Abstract
In wireless sensor networks, clustering is effectively used for many applications, including environment monitoring, because it promises efficient energy consumption for inexpensive battery-operated sensors. The most famous clustering protocol, LEACH (Low Energy Adaptive Clustering Hierarchy), enables the balanced consumption of energy to prolong a network lifetime. In LEACH, however, extra energy and time are consumed to reform clusters at the setup phase of every round. This side effect is worse as the number of clusters increases. This paper presents a novel energy-efficient clustering scheme called COTS (Clustering with One-Time Setup) which removes the cluster-reforming process required at every round after the first round. The proposed COTS allows that the role of the cluster head is rotated among members in a cluster without cluster reforming. By removing the cluster-reforming process, the number of transmissions per round is decreased accordingly. As a result, energy consumption is significantly reduced, resulting in prolonged network lifetime. The simulation study shows that the network performance and lifetime are much improved as the number of clusters is increased.
1. Introduction
Wireless sensor networks (WSNs) consist of many battery-powered sensor nodes (SNs) that monitor their physical surroundings and send the resulting data to a sink node. Since the battery resource directly affects the operation time of sensors, it is very important in prolonging the lifetime of a WSN to design energy-efficient protocols. Thus, many studies in WSNs have focused on delivering the sensed data to the destination while being energy efficient.
Routing in WSNs means that the information from SNs is forwarded to the base station (BS) regularly or on demand. There are two types of routing, classified as flat and hierarchical routing. A clustering approach can be regarded as a hierarchical routing technique. As reported in many studies, clustering schemes can save a lot of energy in WSNs [1, 2]. The clustering associated with data aggregation improves network performance by decreasing the amount of data to be delivered and the number of hops from sensors to the BS. In such networks, however, more energy is consumed in the cluster head (CH) nodes because more computing and communication loads are assigned to the CHs. This non-uniformity of energy consumption among nodes results in some nodes dying earlier than others.
LEACH (Low Energy Adaptive Clustering Hierarchy) is the most famous clustering protocol that resolves the energy unbalancing problem among nodes [3]. In LEACH, nodes are classified into two groups: CHs and SNs. The main idea of LEACH is to reform clusters once every period of time, called a round, in order to rotate the role of the CH among members in a cluster. There have been many studies in the past ten years exploring the LEACH protocol to improve performance. However, there has been no work to address energy consumption during the cluster-reforming process. Since LEACH was developed, many works have been reported. LEACH-C (LEACH Centralized) [4] is one of LEACH's variations, in which cluster heads are elected by a base station to prevent energy imbalance. In HEED (Hybrid, Energy-Efficient Distributed) clustering [5], residual node energy is taken into consideration for the dispersion of energy consumption. In BCDCP (Base station Controlled Dynamic Clustering Protocol) [6], cluster heads are selected from a set of candidate nodes. In TEEN (Threshold sensitive Energy-Efficient sensor Network protocol) [7], a threshold value is set on the basis of LEACH to reduce the energy consumption of CHs and sensor nodes. In APTEEN (Adaptive TEEN) [8] which is a combination of LEACH and TEEN, a time period is set for transmitting data periodically for data accuracy and reliability.
In this paper, we take repetitive cluster reforming over the network lifetime into account for reduced energy consumption and prolonged lifetime in WSNs. During the setup phase of every round in LEACH, the cluster reforming process is carried out by all the nodes in a cluster. That is, every SN transmits at least once, either to inform others that it is a CH or to request to join a chosen cluster. Furthermore, the CH broadcasts the TDMA schedule to all members. Notice again that the setup phase, including communications, is performed at every round in the conventional LEACH protocol.
In this paper, we propose an energy-efficient clustering scheme called COTS (Clustering with One-Time Setup) by removing the cluster-reforming process and adding a rescheduling slot to the end of every round. Usually, the setup phase is composed of hundreds of slots, even though it depends on the number of nodes and the pattern of random access. By skipping this cluster-reforming process, energy is significantly saved. In COTS, the role of the CH is rotated among the members in a cluster by transmitting the cluster head order at the rescheduling slot. As a result, energy consumption is significantly reduced, and the network lifetime is increased accordingly. Our simulation study shows that the proposed COTS remarkably improves network performance and lifetime.
The main idea of the proposed COTS can be summarized in the following steps.
A cluster is formed just one time at the setup phase of the first round. Once a cluster is formed, the CH creates a cluster head list. This list consists of all the other member nodes in order of the closest to the furthest away. This list is used to rotate the role of CH among all other member nodes. The list is broadcasted to all the other members during the setup phase at the first round. In the steady-state phase, the CH collects data from members as in other protocols. If a CH cannot receive data from a member, the CH regards the member as a dead node. At the rescheduling slot every round, the CH creates a new cluster head order based on the last set of collected data packets and then broadcasts the new cluster head order to members. If a member does not receive the order, it simply invalidates the current cluster head order.
The rest of this paper is organized as follows. In the following section, the LEACH protocol's strengths and weaknesses are reviewed in brief. Section 3 presents the proposed COTS algorithm with respect to design principles and operations. The performance of the proposed COTS is evaluated via simulation and compared to the conventional protocol in Section 4. Finally, this paper is concluded in Section 5.
2. Preliminaries
A lot of studies on clustering-based protocols in WSNs have been published. LEACH [3] is one of the most famous clustering techniques. It divides an entire network into groups called clusters. A cluster consists of many SNs and a CH. The CH collects sensed data from SNs and then aggregates and transmits them to the BS. Hence, SNs do not need to communicate with the base station, resulting in a decreased communication burden. Therefore, energy consumption is reduced and network lifetime increased.
In hierarchical approaches such as clustering, the data at the higher levels of hierarchy is more important than those at the lower levels. Thus, communications between CH and BS need more attention compared to intracluster communications, because packet loss between CH and BS means a loss of all the data in a cluster. Therefore, the CH-to-BS signal uses a Carrier Sensing Multiple Access (CSMA) technique, and it is broadcasted to the entire network to avoid the hidden terminal problem. On the other hand, the sensor-to-CH signal uses Time Division Multiple Access (TDMA).
The LEACH protocol repeats a series of setup and steady-state operations with the static time interval called round. As shown in Figure 1, each round consists of two phases: a setup phase and a steady-state phase.
Operation of the LEACH protocol.
2.1. Setup Phase
In the setup phase, clusters are formed, and the TDMA schedule is created for the steady-state phase. Every node wakes up and initializes its internal state as default. Then each node generates a random number between 0 and 1 and compares the number with the
After the election of CHs, all the nodes in a network perform the operation depicted in Figure 2. The left-hand side of Figure 2 represents the behaviors of CHs, while the right-hand side represents those of cluster members. The elected CHs broadcast their existence to all the nodes of the network. SNs receive these advertisements and choose one of the nearest CHs as their CH. An SN sends the cluster join message to the selected CH. Hence, CHs can know all of their members. Each CH creates a TDMA schedule for the steady-state phase and broadcasts the schedule to its members. Finally, cluster members receive the schedule. During the setup phase, every member node sends the Join-Request message to its CH as shown in Figure 2. This causes long delay because a CH has to receive Join-Request messages from its member nodes in a serialized fashion. In COTS, however, the long delay is permanently removed after the first round because there is only one-time setup in COTS, which will be presented in Section 3.
The setup phase in LEACH.
2.2. Steady-State Phase
In the steady-state phase, cluster members sense the surroundings and transmit the sensed data to their CH depending on the TDMA schedule received at the setup phase. SNs go into sleep mode to save energy for other slots. As shown in Figure 3, a steady-state phase consists of a few frames, and a frame can be divided in two time slots: the time slot for the SNs and the time slot for CH. SNs transmit sensed data to their CH in the time slot for CH. The CH compresses (or aggregates) this data and transmits it to the BS. Since a cluster operates in a frame unit, if it does not have enough time for a frame, the cluster will not work in the time left.
Rounds of the LEACH protocol.
2.3. Weaknesses of the LEACH Protocol
Figure 3 shows the rounds of the LEACH protocol. Black squares indicate the setup phase, squares with diagonal lines are multiple TDMA time slots for sensors, and dark gray squares represent the time taken by CHs to compress data and transmit it to the BS. The left side of the dotted line is the initial round, and the right side represents the final round at the end of the network lifetime. It shows a LEACH weakness that the transmission interval depends on the number of members in a cluster [10]. For example, we assume that the time of a steady-state phase is 5 seconds, and all time slots spend 0.1 seconds equally. If the number of members is 10, each SN has 5 transmission time slots. On the other hand, if the number of members is 5, each SN can occupy 10 slots. The fewer the number of alive nodes, the greater the number of detections will happen for a member.
If the detection distance for sensing is not changed, it does not have any advantage to increase the number of detections because decreasing the sensing interval of nodes causes more energy consumption. Thus, creating a TDMA schedule based on the number of living nodes can be disadvantageous in terms of energy efficiency.
Another weakness is caused by the repetitive election of CHs based on the changed probability of the total number of living nodes. Hence, there are differences in the number of clusters between rounds. An increment of the number of CHs decreases total network lifetime, and a reckless decrease causes unbalanced energy consumption between nodes in the entire network.
3. Clustering with One-Time Setup
In this section, we present the operational principles of the proposed COTS. Clusters are formed at the setup phase of the first round, and the first round only. This results in significant energy savings.
Unlike the conventional approaches such as LEACH, the proposed COTS does not require cluster reforming, and thus the cluster membership is not changed over rounds. The CH order is determined at the setup phase of the first round. Every member of a cluster simultaneously changes its CH according to the CH order in the next round. This practice may run into a problem as the number of dead nodes increases over time. That is, if a dead node is to be a CH at the next round, it results in the loss of all packets of a cluster during that round. There is no such problem in the conventional protocols, because clusters are newly formed at every setup phase. In order to avoid this phenomenon, a new or updated cluster head order should be created and broadcasted when nodes are dead. Thus, we introduce a new time slot for rescheduling CHs called a rescheduling slot, which is positioned just before the new round starts.
3.1. One-Time Setup
After all data is received from member nodes, each CH compresses the aggregated data into a single message and then transmits it to the BS. In LEACH, however, this method has a weakness in that the CH cannot send the message to the BS when the CH does not receive any data from members within the steady-state phase. In the actual code of the MIT uAMPS project [3], if CH did not receive the last node's data, it does not compress and transmit data for the BS. This is one of the reasons for LEACH to carry out reclustering per round. However, the proposed COTS does not have a setup phase after the first round, and the cluster membership and the TDMA schedule are not changed at all. So, the TDMA schedule can include unavailable time slots that have been assigned to dead nodes. This is trivial when compared to the significant reduction of energy consumption by removing the setup phase and does not affect performance at all.
3.2. Clustering
COTS is subject to a network topology whose nodes are distributed evenly in the same way as the LEACH protocol. Once clusters are formed after the setup phase, the cluster member is not changed for a network lifetime, even if there are high density areas of nodes that encourage inefficient energy consumption of the specific area. If nodes are distributed uniformly, the network has a lower risk of node concentration.
Figures 4(a) and 4(b) show the cluster state immediately after the setup phase in the network using a LEACH protocol on nodes that are distributed evenly. White points represent SNs, red points are CHs, and black points indicate the best CH position required by each cluster. The best CH position means the CH location that minimizes the total communications cost. A transmission range is a critical factor that affects the energy consumption of nodes. It should be noted that almost all CHs are located in a relatively good position in LEACH, but are not always as good as in Figure 4(a). In the process of cluster reforming, each node measures the distances between CHs and chooses a cluster made by a CH with the shortest distance. Thus, some nodes have no choice but to select the CH located at the relatively bad position from outside the cluster, if the distances to other CHs are longer than the CH. There is the probability that some nodes located in the corner of a network cluster become CHs. Figure 4(b) shows a network with the CHs located in the corner. One glance is enough to know that the position of the CHs is not good. In this case, the transmission length between nodes of a cluster becomes the longest, resulting in higher energy consumption. On the other hand, the black points represent the ideal CH position with the most efficient energy consumption.
Clustering examples of the LEACH protocol.
We can explain the features of the network without cluster reforming by using Figure 5, which shows the state of the clusters in Figure 4(a) after a round. There are three different phenomena as contrasted with the LEACH protocol having reclustering, and we explain these as the three clusters drawn in the figure. The blue cluster shows the worst case of CH positions made by rotating the role of CH within the cluster. If the width and height between two adjacent nodes are taken as 1 unit, the total length for communications of the blue cluster of Figure 4(a) is about 8.4 and for Figure 5 is 16.8. The length of Figure 5 is two times as long as Figure 4(a), but this does not indicate the doubled energy consumption. According to the LEACH energy consumption model, the energy consumption increases as the second or fourth power of the distance, so it has a bad effect on network lifetimes. Thus, we need to know the effect of the longer communication length and the effect of not reforming clusters, comparing the worst cases in cluster nonreforming and reforming, because the worst case affects the lifetime of a network more than the best case. The difference of the members between the two blue clusters is 1, and the difference of the total length is also just 1. If the number of nodes of a network increases, these differences will also increase. The more important thing is that the cluster with fixed cluster members for rounds will inevitably have all cases, including the worst case, when the network has enough rounds. Otherwise, the network that reforms has more good cases, because the new elected clusters have new members, which join depending on distance. Nodes (1, 1) and (2, 2) of Figure 5 belong to the blue cluster, although these are closer to the green cluster. Likewise, node (5, 2) also cannot join the blue cluster. Removing cluster reformation removes the chances for some nodes to participate in reasonable clusters and therefore increases the total communication length. In other words, the flexibility of clustering is decreased by fixing the members of a cluster. For these reasons, a protocol without cluster reformation needs to minimize the negative effects of fixed clusters. To do so, COTS creates the CH order based on how far each node is from all other nodes in the cluster during the setup phase. Once the setup phase is finished, the CH knows which other node has the next best position to be the next CH. Thus these nodes can be selected as CHs for the remaining rounds to reduce the negative effects of outlying CHs. The red cluster of Figure 5 has the best positioning compared with those of Figure 4. And with a cluster head order determined by better geographical positioning, the flexibility decrease problems are delayed for as long as possible to only appear near the end of a network's lifetime.
Clustering example of the COTS protocol.
3.3. Dynamic Rescheduling
Figure 6 shows the operational procedure of the steady-state phase in the proposed COTS. CH aggregates the sensed data and transmits it to the BS every round. In the meantime, CH saves a list of living member nodes from which sensed data is successfully received. From the list of living members, a new or updated order of CHs is built. This list will remain in effect until a new CH order is created during another round.
The steady-state phase in COTS.
The order of CHs is rotated for balanced energy consumption. Figure 7 shows the rounds of the COTS protocol including the rescheduling slot. The proposed COTS includes a rescheduling slot every round. In the rescheduling slot, CH has a chance to announce the living status of cluster members. If dead nodes are detected by a CH, the CH announces a new or updated cluster head order to all of the members within the cluster. The member nodes receive the cluster head order. The cluster head order is updated, when there is any difference between the current cluster head order and a new cluster head order. Otherwise, the CH sends alive messages to members to inform them of its survival when any node is not dead during the current round. Hence, every member can know the status of all of the other members, and no dead node is chosen as CH, as depicted by the light gray squares in Figure 7. Figure 8 shows the node operation at the rescheduling slot. The left-hand side of the first question of the flow represents the operation of the current CH, and the right-hand side represents that of member nodes.
Rounds of the COTS protocol.
Operation at the rescheduling slot.
4. Performance Evaluation
In this section, the performance of the proposed COTS is evaluated via extensive simulations using ns-2 [11] and compared with the conventional protocol.
4.1. Simulation Environment
The simulation parameters are shown in Table 1. The initial battery energy assigned to each SN is assumed to be 1 and 2 Joules for different scenarios of energy resource in our simulation. In another simulation, the number of CHs is assigned as 5 and 10 to know what effect the difference of the cluster area has. The ns-2 simulator automatically regulates a limit of transmission of a node described as transmission range by calculating the length between base station and the farthest node. It is for minimizing inefficiency in the energy consumption caused by the cluster head advertisement in setup phases. Note here that, as in most WSNs, the transmission power of nodes is fixed, and their communication range is also fixed.
Parameters for simulation.
For our experiment, we used the energy consumption model [12, 13] provided with the LEACH source code. The propagation model is the same as that of the LEACH protocol, which does not consider errors in wireless channels. Power control can be used to invert this loss by appropriately setting the power amplifier. That is, if the distance is less than a threshold 
The first function of (2) is an energy consumption value spent by the transmission of an electronic device, and the second function is the value by the transmission amplifier. Since receivers do not need to have any amplifiers, it only spends energy for an electronic device as shown in (3). The radio energy consumption for receiving k-bit data is calculated as
4.2. Simulation Results and Discussion
In WSNs, the ultimate goal of energy saving is to prolong the network lifetime. In other words, “reduced energy consumption” means “prolonged lifetime” in WSNs. The network lifetime is indicated by the number of living sensor nodes. The two graphs of Figure 9 show the network lifetime for the different initial energies of 1 and 2 Joules, respectively. For the two scenarios of energy resources, there is an improvement of 34% and 37%, respectively.
The number of living nodes.
In the graphs, the number of living nodes in COTS is less than that in LEACH until 75 and 150 seconds for initial energies of 1 and 2 Joules, respectively. This indicates that the energy is consumed faster. This is due to the beneficial improvement in COTS, which is as follows. Given a period of time, more rounds are carried out in COTS compared to LEACH, because the setup phase is removed every round after the first round in COTS. More rounds mean both more sensing and more transmissions, resulting in more energy consumption during the same period of time. Conceptually, COTS replaces the setup phase by just one time slot, called the rescheduling slot. As a result, the number of frames in COTS is more than that in LEACH. So, both the configuration time and the energy are remarkably decreased.
The two graphs of Figure 10 represent the number of packets accepted by BS. Note that the curves of LEACH and COTS end at the network lifetime of them, respectively, because no packets are accepted by BS after the lifetime. At the beginning of simulation, all nodes in the network are alive, so there is no difference between COTS and LEACH with respect to the number of packets accepted by BS. We can confirm it from the early slope of the two lines drawn as COTS and LEACH in Figure 10. At the middle phase of the simulation, the curve for COTS is more smoothly saturated. The decrease of the slope is based on the fixed frame size, and it shows that our approach works well. Later on in the simulation, the slope of COTS decreased then converged on zero. The longer time in COTS is thanks to the increased lifetime as shown in Figure 9.
The number of packets accepted by BS (with 5 CHs).
In Figure 10, we should pay attention to the relative height of the two graphs, but not the values. The height of the two figures is based on the accepted packets of LEACH. The vertical axis was divided into seven parts by the dotted lines. When the number of cluster heads (CHs) is small, the number of packets accepted by BS is slightly decreased in comparison to LEACH because the communication environment and parameters between sensor nodes (SNs) and their CHs are fixed at the first round and not averaged over the rounds resulting in some undelivered packets in COTS. Note that the cluster-reforming process may probabilistically average the communication environment and parameters between SNs and their CHs over the rounds in LEACH. However, when the number of CHs is large, the number of packets accepted by BS in COTS is more than that in LEACH as shown in Figure 13. Note here that the communication length is relatively short as the number of CHs increases, and, thus, the communication environment and parameters between SNs and their CHs will be more stable. Since the round interval is 10 seconds in these simulations, the system with 2 Joules has about two times as much as the simulation with 1 Joule, so the saved energy affects the total packets sent.
Figure 11 shows the total energy consumption per round. As shown in the figure, COTS consumes much less energy than LEACH. As explained earlier, the setup phase is removed at every round after the first round, and just one time slot for rescheduling is added in COTS, resulting in significantly saved energy. Accordingly, except for the beginning of network lifetime, COTS consumes less energy than LEACH.
The total energy consumption per round.
Figure 12 is the result of a simulation with 10 CHs that can be compared with Figure 9(b), which has 5 clusters. If the end of the network lifetime is defined as 90% of total nodes being dead, the end of lifetime of Figure 9(b) is 150 seconds, and the lifetime of Figure 12 is 300 seconds. The network in Figure 12 lives twice as long as that in Figure 9(b). This is because the fixed members in a cluster decrease flexibility as mentioned in Section 3.2. Increasing the number of clusters indicates the decreased area of each cluster. Therefore, the entire communication length also decreases, resulting in reduced bad effects. The reverse of the bad performance of Figure 9(b) is shown at 60 nodes, and the reverse of Figure 12 is at 80 nodes. Moreover, the staircase phenomenon comes more sharply into focus. It is caused by the energy-aware operation of CH at the steady-state phase. That is, CH stops when the energy of the battery is not enough to send a message to BS. The saved energy will be used at the rescheduling slot to guarantee an agreement of the CH orders among cluster members. It is a fact that the more the number of clusters is, the clearer this phenomenon will be.
The number of living nodes (with 10 CHs).
The number of packets accepted by BS (with 10 CHs).
Figure 13 draws the number of packets accepted by BS. We can realize that the higher CH allows COTS to show its advantages by comparing Figure 13 and Figure 10(b). The greatest strength is the relative increase of the total number of accepted packets. The performance of the accepted packets is reversed, when the network has ten CHs, and it is less than LEACHs when the network has five CHs. This suggests that the network saves more energy than before. It is somewhat surprising that the entire network lifetime is significantly improved even though the total number of packets is higher than that of LEACH during the network lifetime. As estimated from COTS's features, which are the static number of clusters and the data sent at regular intervals, the COTS has much higher reliability than LEACH. This is shown in the higher slope in the graph.
5. Conclusions
The proposed COTS significantly reduces energy consumption incurred by the setup phase of every round by realizing novel clustering without repeated setup, resulting in improved performance and prolonged network lifetime. Once a cluster is formed at the setup phase of the first round, the CH creates the cluster head order and broadcasts it to all the members in the cluster. As a result, the role of CH is rotated among members in a cluster without requiring any cluster-reforming process. The cluster head order is updated and announced to members at the rescheduling slot of every round, after it is checked against any dead member. The features of the COTS protocol can be summarized as follows.
Some nodes die faster than others when using LEACH, but the entire lifetime is remarkably improved. The more CHs there are, the less the lifetime is decreased. The higher the initial energy is, the more energy is saved.
According to our simulation results, the network lifetime is prolonged more than 1.37 times in comparison to LEACH.
