An energy-efficient unequal clustering routing protocol for wireless sensor networks

Abstract

Wireless sensor networks have drawn tremendous attentions from all fields because of their wide application. Maximizing network lifetime is one of the main problems in wireless sensor networks. This article proposes an energy-efficient routing protocol which adopts unequal clustering technology to solve the hot spots problem and proposes double cluster head strategy to reduce the energy consumption of head nodes in the clusters. In addition, to balance the energy consumption between cluster heads and cluster members, a hybrid cluster head rotation strategy based on time-driven and energy-driven is proposed, which can make the timing of rotation more reasonable and the energy consumption more efficient. Finally, we compare the proposed protocol with LEACH, DEBUC, and UCNPD by simulation experiments. The simulation results prove that our proposed protocol can effectively improve the performance in terms of network lifetime, energy consumption, energy balance, stability, and throughput.

Introduction

Wireless sensor network (WSN) is a self-organizing wireless communication network system which consists of sensor nodes, base stations (BSs) (or sink nodes), and terminal systems. The sensor nodes are randomly distributed in the monitoring region to collect the information and transmit the information to the BS (or sink node) by single hop or multi-hop. Finally, the effective information is transferred to the terminal system through the communication links such as the Internet or satellite by the BS. Users can manage the operation of WSN through terminal system. Figure 1 shows the architecture of a WSN.

Figure 1.

Architecture of wireless sensor network.

WSNs have been greatly developed and widely used in industry, agriculture, transportation system, environmental monitoring, medical industry, smart home, and so on, because of many advantages of WSNs such as easy deployment, low cost, self-configure ability, and unattended operation. However, sensor nodes are powered by the battery which is energy limited and hard to replace. That affects performance, quality, and lifetime of WSNs. So, the control of the energy consumption becomes a major problem in WSNs.

In the original idea, each sensor node collects and sends data directly to the BS. In this case, the long communication distance leads to the high energy consumption. Meanwhile, the congestions and collisions will occur when a large number of nodes transmit data at the same time, which causes more data retransmission and energy consumption. To solve these problems, many methods have been proposed. Thereinto, cluster-based routing protocol for WSNs has been proved to be very effective approach. In clustering mechanism, nodes are organized into clusters which consist of cluster heads (CHs) and cluster members (CMs). CMs collect and send the data to their respective CH. CHs take charge of data aggregation/fusion to reduce data redundancy and forward processed data to the BS through single hop or multi-hop. Clustering techniques in WSNs have many advantages such as high energy efficiency, low redundancy, collision avoidance, latency reduction, and so on. However, there are some problems in cluster-based protocols. In a large scale of network, multi-hop communication mode is usually adopted in order to save energy. In this scenario, the CHs closer to the BS will take on more forwarding tasks, which results in heavy overhead of CHs, and these CHs will run out of power earlier than other nodes. It causes breakdown of the cluster and the communication lost between CHs. This is called “hot spots” problem. In addition, because CHs are responsible for aggregating/fusing data received from member nodes and forwarding data to BS, the CHs consume more energy than CMs, which also leads to energy unbalance of overall network.

In order to solve these problems mentioned above, an energy-efficient unequal double cluster head (UDCH) routing protocol is proposed in this article. In UDCH protocol, unequal clustering technology is adopted to solve the hot spots problem. Similar to other unequal cluster algorithms, the cluster size is related to the distance to the BS. The CH closer to the BS takes more forwarding tasks, so cluster size should be smaller to reduce the overhead of CH. Meanwhile, UDCH considers the energy of CH as another metric in cluster size decision besides the distance. The CHs with more residual energy will form larger clusters. In order to reduce the overhead of the CHs, UDCH proposes the double CH strategy. In this strategy, each cluster has two CHs. Main head is responsible for forwarding data between the clusters and vice head is responsible for receiving and aggregating data within each cluster. The election mechanism of CHs directly affects the quality of the cluster and energy efficiency of the network, UDCH proposes different election mechanisms for main head and vice head. The main CH selection algorithm is improved where a multi-objective optimization technique is introduced to calculate the cost value for each candidate main head. In the selection method of vice head, we consider the residual energy and communication distance. By the improved double-CH method, energy can be saved and balanced. In addition, to balance the energy consumption between CHs and CMs, a hybrid CH rotation strategy based on time-driven and energy-driven is proposed in UDCH protocol. In this work, we combined their advantages of two types of rotations for main CH rotation. Energy-driven rotation strategy is adopted in the initial stage, and it is replaced by time-driven rotation strategy when energy efficiency of energy-driven strategy is lower than time-driven strategy. This article gives a method to calculate the conversion time of two modes. Through this hybrid CH rotation strategy, the timing of rotation is more reasonable and the energy consumption is more efficient.

The rest of this article is organized as follows. Some well-known routing protocols proposed for WSNs are summarized in section “Related works.” Section “Network and energy model” describes the network model and energy model in this work. Section “UDCH protocol” describes proposed routing protocol UDCH in detail. Section “Simulation and discussion” presents the simulations and performance evaluation of UDCH. In the last section, the work is concluded.

Related works

The cluster-based routing protocol is typical hierarchical routing protocol. The structure of network based on cluster is shown in Figure 2. The main idea is that the whole network is divided into small sets of nodes, called cluster. Each cluster contains CH and CMs. CH is responsible for managing its CMs and forwarding data, which is elected in a certain rule. Many typical hierarchical routing protocols have been proposed, such as LEACH, ¹ PEGASIS, ² HEED, ³ and so on.

Figure 2.

Structure of network based on cluster: (a) one-hop network and (b) multi-hop network.

In recent years, some improved cluster-based routing protocols based on these typical protocols have appeared. In view of the restriction that all nodes in LEACH need to communicate directly with the BS, an improved ant colony algorithm is introduced to optimize the multi-hop path of the CHs to the BS. ⁴ In the selection of CH stage, the energy consumption and the density factor are considered as selection metrics. LEACH-CS calculates the optimal number of CHs and introduces second head to reduce the energy consumption of the CHs and balancing the energy consumption of the network. Zhenlei and Feng ⁵ proposed an improved LEACH-C protocol (LEACH-CMS) based on multi-hop routing and intelligent sleeping mechanism. In Ahamad and Kumar, ⁶ fuzzy logic algorithm is applied to CH selection by introducing two fuzzy variables: the distance from the BS and the remaining energy. And the multi-hop routing algorithm is used to effectively improve the network lifetime. In view of the “hot spots” problem caused by the unbalanced energy consumption in WSNs, an unequal cluster routing protocol (ECBUC) based on energy consumption is proposed, which considers the residual energy and relative position information of each node in the network. ⁷ In the clustering process, the cluster radius is controlled according to the distance from BS. The path influence factor is put forward, such as residual energy, location information, and so on. The inter-cluster routing path is established by choosing the nodes with higher path influence factor. Lei et al. ⁸ improved the CH selection strategy and inter-cluster multi-hop routing algorithm based on unequal clustering route protocol. The specific solutions include the threshold value setting and the calculation of an unequal clustering competition radius. Zhi ⁹ proposed an improved unequal clustering algorithm for WSNs with multi-objective harmony search. The multi-objective optimization problem model is built and works out by the binary harmony search optimization algorithm. In order to solve the “hot spots” problem after clustering, Guiloufi et al. ¹⁰ proposed a new unequal clustering algorithm called energy degree distance unequal clustering algorithm (EDDUCA). It aims to balance energy consumption and maximize the network lifetime. EDDUCA uses the “Sierpinski triangle” method in order to divide network into unequal clusters. Changjiang et al. ¹¹ proposed a distributed energy-balanced unequal clustering routing protocol (DEBUC). It adopts an unequal clustering mechanism, in which clusters closer to the BS have smaller size. For inter-cluster communication, DEBUC adopts an energy-aware multi-hop routing system to reduce and balance the energy consumption of the CHs. The simulation results show that it has better performance than LEACH and EEUC. Zhang et al. ¹² proposed a novel unequal clustering routing protocol considering energy balancing based on network partition and distance (UCNPD). The network area is portioned based on the distance from node to the BS and unequal clusters are built by setting different competitive radius. A modified CH selection algorithm based on LEACH (LEACH-M) was proposed by Zhao et al. ¹³ Based on distributed address assignment mechanism (DAAM) of ZigBee, both residual energy and network address of nodes are taken into account to optimize CH threshold equation. Furthermore, by leveraging a CH competitive mechanism, LEACH-M successfully balanced the network energy burden and dramatically improved energy efficiency. Sara and Ridha ¹⁴ introduced a new rule for CH selection and round time computing based on the remaining energy. And a multi-hop communication model is integrated in the WSN using two operating processes: leveling and generic multi-hop routing. Zhao et al. ¹⁵ introduced a new network structure model and combined the original energy consumption model to construct a new method to determine the optimal number of clusters. Yang et al. ¹⁶ presented an unequal cluster-based routing scheme for WSNs with multi-level energy heterogeneity called UCR-H. It calculates the number of clusters in each unit by balancing energy consumption among the CHs in different units and finds the optimal number of units by minimizing the total energy consumption of inter-cluster forwarding. Finally, the size of clusters in each unit is elaborately designed based on node’s energy level and the number of clusters in the unit.

Network and energy model

Network model

In this work, suppose that sensor nodes are randomly scattered in a two-dimensional (2D) square area; BS is out of monitoring area and has unlimited power; all sensor nodes and BS are stationary; each node can adjust their communication range and estimate the distance; each sensor node has unique ID and know its own location; each sensor node has limited power; each cluster has two CHs, called main head and vice head; the main CH of each cluster takes part in the multi-hop routing; the vice CH collects data from CMs and transmits the aggregated data to main CH.

Energy model

The vast majority of energy is consumed by the communication, so the energy consumption of sensing and processing is neglected in this work. In the process of communication, transmitting and receiving consume more energy than monitoring and sleeping. Therefore, we only consider the energy consumption of transmitting and receiving as energy consumption of communication. The radio model in this work is the same as described by Soro and Heinzelman. ¹⁷ The energy consumed by transmitting l bit data can be calculated as in formula (1)

$$E_{\mathrm{TX}}(l,d)=\{\begin{array}{c}l{E}_{\mathrm{elec}}+l{\epsilon }_{\mathrm{fs}}{d}^2,d\le d_0\hfill \\ \multicolumn{1}{c}{l{E}_{\mathrm{elec}}+l{\epsilon }_{\mathrm{mp}}{d}^4,d\ge d_0}\end{array}$$ (1)

where $E_{\mathrm{elec}}$ is the energy consumption for sending or receiving 1 bit data, l is length of transmission data, ${\epsilon }_{\mathrm{fs}}$ is the coefficient of energy consumption for amplifying radio at free-space mode, ${\epsilon }_{\mathrm{mp}}$ is the coefficient of energy consumption for amplifying radio at multi-fading mode, d is the communication distance, and d₀ is the threshold value, $d_0=\sqrt{{\epsilon }_{\mathrm{fs}}/{\epsilon }_{\mathrm{mp}}}$ .

Consumed energy of receiving m-bit data is calculated by formula (2)

$$E_{\mathrm{RX}}\left(m\right)=m{E}_{\mathrm{elec}}$$ (2)

where $E_{\mathrm{elec}}$ is the energy consumption for sending or receiving 1 bit data, and m is the length of the data.

In this work, we assume that each node sends same length data to its CH, and CH aggregates data into a fixed length packet.

UDCH protocol

The unbalance of energy consumption is the main reason for the hot spots problem. In the multi-hop network, the CHs closer to BS will consume more energy than other CHs due to taking more forwarding tasks. In order to solve this problem, an energy-efficient UDCH routing protocol is proposed in this section. In UDCH, clusters have different sizes in different regions. The cluster size is small when the cluster is close to BS. So, there are more CH nodes in these areas to share the data relay tasks, which can avoid the premature death of the CHs effectively. Second, in order to reduce the load of CHs, the vice CH mechanism is proposed. The main CH is responsible for data communication and relaying. The vice CH is responsible for data collection, aggregation, and cluster maintenance within each cluster. Third, to balance the energy consumption between CHs and CMs, a hybrid CH rotation mechanism based on time-driven and energy-driven is proposed in UDCH protocol. The rotation mechanism can effectively reduce energy consumption caused by cluster reformation. The architecture of network based on UDCH protocol is shown as Figure 3.

Figure 3.

Architecture of network based on UDCH protocol.

The UDCH protocol contains four phases: initialization, cluster set up, data transmission, and CH rotation.

Initialization phase

In order to balance energy of whole network, unequal cluster mechanism is adopted in the UDCH protocol. The forwarding load is heavier when the node is closer to the BS. Hence, the size of cluster closer to the BS should be smaller than cluster far away from BS. Meanwhile the residual energy of CHs should be considered as a metric. The cluster size is related to competition. In order to generate unequal cluster, each node needs to calculate its own competition radius Rc.

The initialization phase includes two steps: competition radius calculation and information collection. In first step, the BS transmits a B_hello message directly to all sensor nodes. Each sensor node estimates the distance to BS according to the received signal strength indicator (RSSI) once B_hello message has been received. Formula (3) of Rc is as follows

$$\begin{array}{c}\multicolumn{1}{c}{\mathrm{Rc}(S_i)=(\beta \frac{E_{\mathrm{res}\mathrm{\_}i}}{E_{\mathrm{init}}}+\alpha \frac{d_{\mathrm{itobs}}}{D_{max}})R_{max},0<\alpha \le 1,}\\ \multicolumn{1}{c}{0\le \beta <1,\alpha +\beta =1}\end{array}$$ (3)

where $E_{\mathrm{res}\mathrm{\_}i}$ is the residual energy of node $S_i$ , $E_{\mathrm{init}}$ is the initial energy of $S_i$ , $d_{\mathrm{itobs}}$ is the distance from $S_i$ to BS, $D_{max}$ is the maximum distance from sensor nodes to the BS, $\alpha$ and $\beta$ are weighted value to adjust the proportion of energy and distance, and $R_{max}$ is the predefined maximum competition radius. In our work, $R_{max}$ is the maximum communication rang.

In the second step, all sensor nodes broadcast a packet, called SHMSG. The content of the package contains node id, residual energy, and packet type (packet type = 1). Each node records the information of neighbors according to SHMSG packets received and calculates average energy of its neighbor nodes. Meanwhile, each node records the number of its neighbors which is called “degree.” The format of the SHMSG packet is shown in Table 1.

Table 1.

Format of SHMSG packet.

Packet type = 1

Node ID

Energy_res

Cluster set up phase

There are three steps in cluster formation phase: main CH selection, cluster formation, and vice CH selection.

Main CH selection

The CH selection technique affects the performance of cluster-based protocol. In the UDCH, each node computes a delay time Td, which is calculated by formula (4)

$$\mathrm{Td}\left(S_i\right)=(1-\frac{E_{\mathrm{res}\mathrm{\_}i}}{E_{\mathrm{avg}\mathrm{\_}i}})*\mathrm{Tc}+\mathrm{rv}.$$ (4)

where $E_{\mathrm{res}\mathrm{\_}i}$ is the residual energy of node $S_i$ , $E_{\mathrm{avg}\mathrm{\_}i}$ is the average energy of $S_i$ ’s neighbors, Tc is preset based on experience which represents the competition time of main CH, rv is the random value in [0,0.5]. When many nodes have the same residual energy, $\mathrm{rv}$ plays a role in reducing communication conflicts.

After Td expires, the node becomes candidate CH and broadcasts the CCHMSG packet within its competition radius. The content of CCHMSG packet includes ID, residual energy, and packet type (packet type = 2). The format of the CCHMSG packet is shown in Table 2.

Table 2.

Format of CCHMSG packet.

Packet type = 2

Node ID

Energy_res

If one node receives CCHMSG packet before its delay time Td expires, it will become a common node and sleep. If one candidate CH receives the CCHMSG packet from other nodes before the competition time Tc expires, it will compare the residual energy between them. If its energy is lager, it becomes the final main CH; otherwise, it becomes common node. It is to be noted from formula (4) that the nodes with larger remaining energy have higher probability for CH selection.

The final main CHs broadcast MCHADV message within competition communication rang when time Tc expires. The message MCHADV maintains node ID, residual energy, distance to BS, and degree. The format of the MCHADV packet is shown in Table 3.

Table 3.

Format of MCHADV packet.

Packettype = 3

Node ID

Energy_res

Distanceto BS

Degree

BS: base station.

The procedure of main CH selection is shown in Algorithm 1.

Algorithm 1. Main CH selection algorithm

BS broadcasts B_hello message to all nodefor each node Si doreceive B_hello messagecompute Si’s RC according to formula (3)broadcast SHMSG messageendfor each node Si doreceive SHMSG messages from all neighborscalculate Si.degree and Si.E_avgcompute Si. TdSi.type = 0while Si. Td ≠ 0if Si receives CCHMSG message from SjSi becomes common node Si.type = 1sleependendif Si.type == 0Si becomes candidate CH Si.type = 2Si broadcasts CCHMSG messageendwhile Si. Tc ≠ 0if Si receives CCHMSG message from Sjif Si.type == 2if Si.energy < Sj.energySi becomes common node Si.type = 1endendendendif Si.type == 2Si becomes CH Si.type = 3Si broadcasts MCHADV messageendif Si.type == 1Si wakes upendend

Cluster formation

Once the competition time Tc expires, all nodes wake up from sleep state, CHs begin to broadcast MCHADV message, and common nodes wait for these messages. If a common node receives the MCHADV message from S_j, it adds the S_j to its list of candidate cluster header nodes (CH_list) and becomes non-CH state. In this phase, a common node may receive several MCHADV messages from different CHs. In this case, how to select an optimal node as its CH is the key issue for clustering. To solve this problem, a cost value is set to each CH. If a common node receives multiple MCHADV messages from different CHs, it will select the node with maximum cost value as its main CH. If two or more CHs have the same maximum cost value, the CH with minimum ID is selected. The cost value is calculated as shown in formula (5). Each non-CH node only selects one CH and transmits a CMJ message to its selected CH

$$\begin{array}{c}\multicolumn{1}{c}{\cos t\left(i\right)=\gamma \frac{E_{\mathrm{res}\mathrm{\_}i}}{E_{\mathrm{init}}}+\theta (1-\frac{\mathrm{degre}{\mathrm{e}}_{\_i}}{N})+\mu (1-\frac{d_{\mathrm{toi}}}{d_{\mathrm{tobs}}}),}\\ \multicolumn{1}{c}{0<\gamma \le 1,0\le \theta <1,0<\mu \le 1,\gamma +\theta +\mu =1}\end{array}$$ (5)

where $E_{\mathrm{res}\mathrm{\_}i}$ is the residual energy of CH _i , $E_{\mathrm{init}}$ is the initial energy, $\mathrm{degre}{\mathrm{e}}_{\_i}$ is the number of CH _i ’s neighbor nodes, N is the total number of all sensor nodes, $d_{\mathrm{toi}}$ is the distance from non-CH node to CH _i , $d_{\mathrm{tobs}}$ is the distance from non-CH node to the BS, and $\gamma$ , $\theta$ , and $\mu$ are adjustment factor.

It can be seen from formula (5) that in the process of selecting its head node for a common node, we consider three factors: residual energy, degree, and distance. From the perspective of energy balance, the candidate CH with larger residual energy in the CH_list is more likely to be selected. However, if the CH Si with larger residual energy has many neighbors, Si maybe has many CM nodes. In this case, common node selects Si as its CH will increase the load of Si. So, the degree of candidate CH is also considered. The candidate CH with smaller degree has greater possibilities to be selected. In view of reducing energy consumption, communication distance is as short as possible. So, candidate node nearer to common node is probably selected. According to formula (5), the common nodes will choose the candidate CH with larger residual energy, fewer neighbor nodes, and shorter distance from CH_list as the its CH. The proportional weight of the three factors can be adjusted by the coefficient $\gamma$ , $\theta$ , and $\mu$ .

If one common node receives no MCHADV message until formation time expires, it will become CH and form a cluster which has only a CH. When the main CH receives the CMJ message from any node, it will take the node as its CM and add node’s ID into its CM_list. The format of the CMJ packet is shown in Table 4.

Table 4.

Format of CMJ packet.

Packet type = 4

Node ID

Energy_res

Location

The procedure of cluster formation is shown as algorithm 2.

Algorithm 2. Cluster formation algorithm
for each node Si do  if Si.type == 1   if Si receives MCHADV message from Sj    Si.CHlist = Si.CH_list ∪ Sj   calculate Sj’s cost according to formula (5)   end   if Si.CHlist ≠ null    Si.head = max(Si.CH_list.cost)     Si sends CMJ message to its head node  else    Si becomes CH Si.type = 3  endendif Si.type == 3  if Si receives CMJ message Sj    Si.CMlist = Si.CM_list ∪ Sj  end endend

Vice CH selection

In order to alleviate the task load of CHs, we propose a double-CH mechanism. The main CH is responsible for communication, and the vice CH is responsible for data collection and maintenance within the cluster. The election principle of the vice CHs aims to minimize the energy consumption in the cluster. In this work, we assume that the shape of a cluster is similar to a circular; m sensor nodes are evenly distributed in the cluster; the distance between any two nodes in the cluster is represented by d. The idea of vice CH selection is to minimize energy consumption as much as possible in the cluster. We can see that the energy consumption of transmission is related to the communication distance from formula (1). Therefore, the problem of vice CH election can be transformed into a minimization problem of distance from all nodes to vice CH (min $\sum d^2$ ). Assuming that the coordinates of vice CH are (x, y) and the coordinates of CM node S_i are (x_i, y_i), the distance from S_i to vice CH in the cluster is calculated by formula (6)

$$d_i^2={(x_i-x)}^2+{(y_i-y)}^2$$ (6)

The expectation of the square of the distance between the CM and the vice CH is shown in formula (7)

$$E\left[d_i^2\right]=\int \int [{(x_i-x)}^2+{(y_i-y)}^2]\rho (x_i,y_i)d{x}_{i}d{y}_i$$ (7)

where $\rho (x_i,y_i)$ is probability density function, and (x, y) is coordinates of vice CH.

Assuming that the origin of coordinates coincides with the center of the cluster and the radius of the circle is R, formula (7) can be simplified as in formula (8)

$$E\left[d_i^2\right]=\rho [\frac{\pi R^4}{2}+\pi R^2(x^2+y^2)]$$ (8)

Assuming that the sensor nodes are evenly distributed, there is $\rho =1/\pi R^2$ . Formula (9) can be obtained by formula (8)

$$E\left[d_i^2\right]=\frac{R^2}{2}+(x^2+y^2)$$ (9)

If there are M CMs in the cluster, the sum of distance from CMs to vice CH is described by formula (10)

$$\sum d_i^2=M[\frac{R^2}{2}+(x^2+y^2)]$$ (10)

To minimize the energy consumption of intra-cluster, the value of $\sum d_i^2$ should reach minimum, which means the value of $x^2+y^2$ should be smallest. Assumption is made that the origin of coordinates coincides with the center of the cluster. It can be seen that the node closer to the center consumes less energy. Based on the analysis above, the vice CH can be selected by formula (11)

$$p_i=\phi \frac{1}{d_{\mathrm{itoc}}}+\eta \frac{E_{\mathrm{res}\mathrm{\_}i}}{E_{\mathrm{total}}}0\le \phi \le 1,0\le \eta \le 1,\phi +\eta =1$$ (11)

where $p_i$ is the selection probability of node S_i as vice CH, $d_{\mathrm{itoc}}$ is the distance between node S_i and cluster geometry center, ${E_{\mathrm{res}\mathrm{\_}}}_i$ is the current residual energy of node S_i, $E_{\mathrm{total}}$ is the total energy of all nodes in the cluster, and $\phi$ and $\eta$ are the adjustment coefficients. The selection probability of each CM in the cluster is calculated by main CH according to formula (11). In the selection of vice head, two factors are considered: distance to the geometry center ( $d_{\mathrm{itoc}}$ ) and residual energy ( $E_{\mathrm{res}\_i}$ ). $d_{\mathrm{itoc}}$ affects the energy consumption of intra-cluster communication, meanwhile, to balance energy consumption, node’s individual energy should be considered. The selection probability of vice head is the tradeoff between energy consumption of intra-cluster communication and node’s residual energy. The CM with large energy and closer to the cluster center is more likely to be selected as the vice CH. The proportional weight of the two factors can be adjusted by coefficients $\phi$ and $\eta$ .

The main CH broadcasts the VHADV message to CMs within the cluster. The VHADV message includes packet type, vice CH’s ID, and main CH’s ID. Each CM compares the vice CH’s ID to its ID, after receiving the VHADV message. The node with the same ID becomes vice CH. The format of the VHADV packet is shown in Table 5.

Table 5.

Format of VHADV packet.

Packet type = 5

Vice CH ID

Main CH ID

CH: cluster head.

Data transmission

After clusters set up phase, each vice CH creates a TDMA schedule and broadcasts schedule to its all CMs. Based on the allocated time slot, each CM collects and sends data to its corresponding vice CH. In order to reduce the communication burden, the vice CH applies aggregation technique to process the data once it receives data from all CMs. Then the aggregated data are sent to the corresponding main CH. Finally, main CHs transmit the data to the BS by multi-hop routing.

CH rotation strategy

The unbalanced energy consumption between CHs and CMs causes unbalanced energy consumption throughout the network and affects the network lifetime. Therefore, the CH rotation strategy is used to balance the energy consumption of CHs and CMs. Based on the CH rotation strategy, each node has the opportunity to take on the CH.

Nowadays, the CH rotation strategy is mainly divided into two types: time-driven rotation and energy-driven rotation. The time-driven rotation strategy can balance the energy consumption of the network well. However, the rotation time of each round is difficult to determine. If the rotation time is too short, it will cause the CH rotation to be frequent, and the system overhead to be higher. If the rotation time is too long, it has no effect on balancing the energy consumption. Moreover, CH rotation can cause the interruption of network function and the increasement of network energy consumption. The energy-driven rotation strategy can restrict the influence of rotation in a minimal range. With the reduction in the remaining energy of the CHs, the energy used in the data transmission will be less and less. The energy of CHs will soon reach the energy threshold, the whole network will fall into the constant rotation election, and the energy for the sensing and transmission will be very few. The energy efficiency will become very low. So, in order to minimize the energy waste and maximize the network lifetime, a suitable energy threshold is required. Because double-CH mechanism is adopted in UDCH protocol, the CH rotation strategy is very important for network performance. UDCH proposes a new hybrid CH rotation strategy.

The rotation of main CHs can cause the reconstruction of network topology and generate control overhead. Therefore, rotation in the whole network should be reduced. In the initial stage of network, energy-driven rotation strategy can achieve high energy efficiency due to the sufficient energy; nevertheless, the time-driven rotation can produce a large number of topology reconfiguration overhead. The energy efficiency based on energy-driven rotation strategy will gradually decrease when the network energy is low. In the low-energy stage, time-driven rotation strategy can achieve a high energy efficiency. So, we adopt hybrid main CH rotation strategy based on energy-driven and time-driven in UDCH. The vice CH rotation happens in each cluster and communication overhead is small; therefore, we adopt rotation strategy based on time-driven for vice CHs.

In general, the network topology process of cluster-based routing protocol is built on rounds. Each round is composed of two phases: cluster set-up phase and steady-state phase. The process is shown in Figure 4.

Figure 4.

Clustering process.

The aim of rotation is that more energy can be used for data collection and transmission in steady state. Energy-driven rotation strategy is adopted in the initial stage, and it is replaced by time-driven rotation strategy when energy efficiency of energy-driven strategy is lower than the time-driven strategy. The energy efficiency is defined in formula (12)

$$\epsilon =\frac{E_{\mathrm{steady}}}{E_{\mathrm{steady}}+E_{\mathrm{set}\_\mathrm{up}}}$$ (12)

where $\epsilon$ is the energy efficiency, $E_{\mathrm{steady}}$ is the energy used for sensing and transmitting data in steady-state phase, and $E_{\mathrm{set}\_\mathrm{up}}$ is the energy used for CH selection and cluster formation.

We assume that there are k rounds of data transmission in the steady-state phase in the time-driven rotation strategy. The energy efficiency of the time-driven strategy is calculated by formula (13)

$${\epsilon }_T=\frac{k(E_{\mathrm{CH}}+E_{\mathrm{CM}})}{E_{\mathrm{set}\_\mathrm{up}}+k(E_{\mathrm{CH}}+E_{\mathrm{CM}})}$$ (13)

where $E_{\mathrm{CH}}$ is energy consumption of main CHs in each round data transmission, $E_{\mathrm{CM}}$ is the energy consumption of CMs and vice CHs in each round data transmission, $E_{\mathrm{steady}}=k(E_{\mathrm{CH}}+E_{\mathrm{CM}})$ .

In the energy-driven rotation strategy, if the residual energy of main CH falls below a threshold, the rotation will carry out in the whole network. The threshold is shown in formula (14)

$${\lambda }_i=\tau E_{\mathrm{res}\_i}0<\tau <1$$ (14)

where ${\lambda }_i$ is the threshold of rotation, and $E_{\mathrm{res}\_i}$ is the initial energy of CH _i after each cluster sets up. The energy efficiency of the energy-driven strategy is calculated by formula (15).

$$\begin{array}{cc}\multicolumn{1}{c}{{\epsilon }_E}& =\frac{\xi (E_{\mathrm{CH}}+E_{\mathrm{CM}})}{E_{\mathrm{set}\_\mathrm{up}}+\xi (E_{\mathrm{CH}}+E_{\mathrm{CM}})}\hfill \\ \multicolumn{1}{c}{\xi }& =\frac{(1-\tau )E_{\mathrm{res}\_i}}{E_{\mathrm{CH}}}\hfill \end{array}$$ (15)

where $\xi$ is the round number of data transmission

In the initial stage of network, energy-driven rotation strategy is adopted. While ${\epsilon }_E$  =  ${\epsilon }_T$ , it is replaced by the time-driven rotation strategy. According to ${\epsilon }_E$  =  ${\epsilon }_T$ , formula (16) is obtained

$$\frac{k(E_{\mathrm{CH}}+E_{\mathrm{CM}})}{E_{\mathrm{set}\_\mathrm{up}}+k(E_{\mathrm{CH}}+E_{\mathrm{CM}})}=\frac{\xi (E_{\mathrm{CH}}+E_{\mathrm{CM}})}{E_{\mathrm{set}\_\mathrm{up}}+\xi (E_{\mathrm{CH}}+E_{\mathrm{CM}})}$$ (16)

From formula (16), the energy threshold $E_{\mathrm{res}\mathrm{\_}i}^{*}$ of CH _i can be obtained by formula (17). When the energy of CH _i is below $E_{\mathrm{res}\mathrm{\_}i}^{*}$ , network system begins to use time-driven rotation strategy

$$E_{\mathrm{res}\mathrm{\_}i}^{*}=\frac{k{E}_{\mathrm{CH}}}{(1-\tau )}$$ (17)

We assume all data are aggregated to m-bit data in each round in each cluster. For each main CH, the $E_{\mathrm{CH}}$ is calculated by formula (18)

$$E_{\mathrm{ch}}=m{E}_{\mathrm{elec}}+m{\epsilon }_{\mathrm{fs}}{d}^2$$ (18)

In the initial stage of network, once a cluster is formed, the main CH calculates the $E_{\mathrm{res}\mathrm{\_}i}^{*}$ . After data transmission in each round, the main CH compares the residual energy and $E_{\mathrm{res}\mathrm{\_}i}^{*}$ . If the residual energy is smaller, CH sends rotation strategy conversion message to BS, and then BS broadcasts rotation strategy conversion message to all main CHs. After CHs receive the message, they change strategy into time-driven rotation strategy. The flow chart of main CH rotation algorithm is shown in Figure 5.

Figure 5.

Flow chart of main CH rotation algorithm.

Simulation and discussion

In our works, many simulation experiments are implemented using MATLAB 7.0 to compare UDCH with LEACH, EEUC, DEBUC, and UCNPD. In each group of simulation, we all deployed 400 sensor nodes in a 200 m × 200 m 2D area for fair comparison. The BS locates at (100, 250). Initial energy is 0.3 J. The maximum communication range of each sensor node is 100 m. Every sensor node can store 10 data packets in its memory. A data packet length is 200 bytes, SHMSG packet length is 5 bytes, CCHMSG packet length is 5 bytes, MCHADV packet length is 8 bytes, CMJ packet length is 7 bytes, and VHADV packet length is 3 bytes. Table 6 shows the parameters in simulations. The final simulation results are taken as an average of 10 different results.

Table 6.

Parameters of simulation.

Parameters	Values
Monitoring area	200 m × 200 m
Number of nodes	400
Initial energy of nodes	0.3 J
Data packet size	200 byte
Maximum communicationrang	100 m
$E_{\mathrm{elec}}$ , ${\epsilon }_{\mathrm{fs}}$ , ${\epsilon }_{\mathrm{mp}}$	50 nJ/bit, 10 pJ/bit/m2,0.0013 pJ/bit/m4
Competition radiuscoefficient, $\alpha +\beta =1$	0.7 + 0.3 = 1
Waiting time, Tc	5 s
Cost value coefficient, $\gamma +\theta +\mu =1$	0.4 + 0.3 + 0.3 = 1
Vice CH selection coefficient, $\phi +\eta =1$	0.5 + 0.5 = 1
$E_{\mathrm{res}\mathrm{\_}i}^{*}$ coefficient $\tau$ , k	0.25, 20

CH: cluster head.

Stability comparison

The number of clusters is a very important indicator in hierarchical routing. It can reflect the stability of the clustering algorithm. A stable cluster-based protocol should generate more consistent number of clusters in each round to optimize the energy consumption of the network. The respective distribution statistics of number of clusters after each algorithm that runs at 1000 rounds are shown in Figures 6–9. It can be seen from Figure 6 that the number of clusters is from 5 to 55 which fluctuates greatly in LEACH protocol; it is because CH selection algorithm is based on random number and threshold mechanism in LEACH. Figures 7 and 8 show that the number of clusters is mainly scattered from 15 to 30 in DEBUC protocol and from 5 to 20 in UCNPD protocol. The number of clusters is centralized in DEBUC and UCNPD, because they both consider energy and distance in selection method. Figure 9 shows the simulation result of UDCH protocol under the same conditions. From Figure 9, we can see that the number of clusters centrally distributes from 5 to 15. It indicates that the number of clusters can maintain a basic balanced amount by UDCH protocol. That is because that CH selection considers the energy, degree, and distance. Moreover, distance and energy both are considered in the competition radius calculation. These factors can effectively control the number of clusters. Compared to other three protocols, UDCH protocol has the better stability.

Figure 6.

Distribution of the number of clusters in LEACH.

Figure 7.

Distribution of the number of clusters in DEBUC.

Figure 8.

Distribution of the number of clusters in UCNPD.

Figure 9.

Distribution of the number of clusters in UDCH.

Lifetime comparison

The time of the first death node appearance also can reflect stability of network to a certain extent. The comparison simulations of LEACH, DEBUC, UCNPD, and UDCH are implemented. The final simulation result is shown in Figure 10. In the LEACH protocol, the first nodes died at 190 rounds approximately. In the DEBUC and EERBLC protocol, the first nodes died at 1000 rounds approximately. In the UDCH protocol, the first nodes died at 1220 rounds approximately. In the LEACH, a large number of redundant data packets are generated, and residual energy of node is not considered. That leads to premature death of nodes. In the DEBUC and UCNPD, energy is a major consideration and the unequal clustering technology is used, so the first dead node appears later than LEACH. Especially, UDCH adopts dual-CH and hybrid CH rotation strategy to balance energy of whole network. Hence, the first dead node appears later than other three protocols.

Figure 10.

Stability period.

Network lifetime is very important indicator for evaluating energy efficiency performance. In this work, we take the death of all nodes as end of network lifetime. The network lifetime of four protocols is compared as shown in Figure 11. The simulation results show that lifetime of LEACH is about 1050 rounds, DEBUC is about 1550 rounds, UCNPD is about 1630 rounds, and UDCH is about 1870 rounds. The lifetime of LEACH is shortest due to the redundant data and unbalanced energy consumption. In DEBUC, UCNPD, and UDCH, clustering technology is adopted; therefore, redundant data and energy balance are improved to some extent, and their lifetime is longer than LEACH. In UDCH, hybrid CH rotation strategy reduces control overhead for reconstructing network topology effectively, and double-CH mechanism makes the network energy consumption more balanced. Therefore, lifetime of WSN applied UDCH protocol is the longest.

Figure 11.

Network lifetime.

Throughput comparison

Throughput is defined as the number of data packets successful received at BS. Figure 12 shows results of simulation where the throughput of four protocols is compared. The results show that UDCH receives most packets among four protocols. LEACH receives about 260,000 packets totally during 2000 rounds, DEBUC receives about 500,000 packets, UCNPD receives about 550,000 packets, and UDCH receives about 610,000 packets. LEACH receives most packets before first 500 rounds due to large number of redundant data. After 500 rounds, dead nodes appear in LEACH; therefore, data packet begins to reduce. DEBUC and UCNPD adopt unequal cluster technology, so the distribution of the cluster is more reasonable and energy consumption is more balanced; the total amount of data packets is more than LEACH. The death of sensor nodes is slowest in UDCH, and the lifetime is the longest; therefore, the total amount of packets is largest.

Figure 12.

Throughput.

Energy consumption comparison

Energy consumption implicitly reflects the status of network lifetime. The simulation results of energy consumption are shown in Figure 13. The energy consumption of LEACH is larger than the other three protocols due to random cluster distribution and redundant packets’ transmissions. DEBUC and UCNPD adopt CH selection algorithm based on residual energy, which leads to more reasonable cluster distribution and more balanced energy consumption; therefore, during the same time, energy consumption is smaller than LEACH. UDCH improves CH selection algorithm and competition radius calculation algorithm, which makes the distribution of clusters more reasonable. The double-CH routing protocol will increase the energy consumption to some extent. However, the increased overhead is small and tolerable. The vice heads can share the workload of the main heads and reduce main heads rotation in whole network, which largely reduce the control overhead of network construction. Moreover, in order to save energy and balance energy, UDCH adopts hybrid CH rotation strategy that reduces control overhead effectively. Hence, the energy consumption of UDCH is less than other three protocols.

Figure 13.

Energy consumption.

For evaluating the performance of energy balance of UDCH, the comparison simulations of LEACH, DEBUC, UCNPD, and UDCH are implemented. Figure 14 shows the comparison result of average residual energy. It can be seen that average residual energy of UDCH is largest in four protocols during whole lifetime. Average of residual energy starts to drop below the half of initial energy from 600 rounds in LEACH, DEBUC, and UCNPD, however, from about 700 rounds in UDCH. Especially, after 1000 rounds, UDCH’s advantage is more obvious. The results indicate that UDCH has better performance of energy balance.

Figure 14.

Average of node’s residual energy.

From the above results of the simulations, we can see that UDCH has the longest network lifetime, the highest stability, and best performance of energy balance. It proves that UDCH is an effective routing algorithm.

Conclusion

The power of sensor nodes is limited and difficult to replace. Therefore, to improve energy efficiency of WSNs, this article proposes an energy-efficient UDCH. This protocol aims to solve problems of high energy consumption and unbalanced energy. UDCH adopts unequal clustering technology to solve the hot spots problem, in which CH selection method and cluster size calculation method are improved. In order to reduce the overhead of the CHs, UDCH proposes the double-CH strategy. In this strategy, each cluster has two head nodes called main head and vice head. The election mechanism of CHs directly affects the quality of the cluster and energy efficiency of the network. So, UDCH proposes different selection mechanisms for main head and vice head. A new vice head selection method based on energy and geometric position is present. In addition, to balance the energy consumption between CHs and CMs, a hybrid CH rotation strategy based on time-driven and energy-driven is proposed in UDCH protocol. Through this hybrid CH rotation strategy, the time of CH rotation is more reasonable and energy consumed is reduced effectively. The simulation results prove that UDCH has better effectiveness compared to LEACH, DEBUC, and UCNPD in terms of network lifetime, energy consumption, energy balance, stability, and throughput.