1 Introduction

A widely used WSN is composed of smart sensors with low power consumption and limited computational and radio power. One of the fundamental services provided by WSN is the monitoring of a specified region under observation. Sensor nodes are randomly distributed in a broad filed; these nodes sense, gather, and transmit physical world information to the base station (BS) for aggregation, analysis, and processing.

WSN applications mainly focus on environmental monitoring, intelligent traffic communication, smart home, military defence, and other related fields [1–3], making it difficult or impossible to effectively charge or replace power batteries in the sensor nodes. Therefore, WSN requires high energy efficiency and long network lifetime. Most of the sensors are also left unattended in the deserted environment, which stringently require low energy consumption and power balance in the whole network. Consequently, reducing sensor energy consumption and prolonging network lifetime are the main objectives of current WSN studies and designs.

The WSN lifetime depends heavily on its inherent routing protocol. Numerous WSN models have been proposed to achieve power balance and energy efficiency. However, these models differ from one another in their approaches to finding a new routing algorithm or modifying an existent one [4, 5]. An increasing number of cluster routing protocols for energy balance in WSN has also been presented.

For example, low-energy adaptive clustering hierarchy (LEACH), one of the most notable hierarchical routing protocols, can extend network lifetime by 15 % compared with other flat routing protocols. Hence, it exerts a far-reaching influence on other cluster routing algorithms proposed later. Analogously, HEED provides an energy-balanced distribution of sensor nodes in the network. The whole network is divided into several clusters, and some cluster heads (CHs) are selected by the interactions among all the sensor nodes (SNs) in WSN. All the data from the SNs are sent to the CH in each cluster, which then forwards these data to the BS in relays through multi-hops.

This study investigates further cluster division in WSN based on HEED with the goal of prolonging network lifetime and saving energy consumption. A cell-clustered routing algorithm that provides an efficacious spatial-temporal distribution of network energy in WSN, namely, CC-HEED, is thus proposed based on the HEED structure. Related simulation conditions are also given in this paper. The resulting protocol, CC-HEED, is compared with other notable protocols on energy efficiency.

The remainder of this paper is organised as follows. In Sect. 2, the CC-HEED network model and power consumption model are presented. Lifetime-related definitions are also noted in this part. In Sect. 3, several prestigious routing protocols are reviewed and some hierarchical protocols (LEACH, HEED) are specifically discussed. Section 4 elaborates the proposed CC-HEED protocol based on HEED, which is comprehensively analysed in terms of network lifetime and energy efficiency. Correspondingly, simulations on lifetime distribution in CC-HEED compared with other protocols are presented in Sect. 5. Section 6 concludes the paper.

2 The WSN Model

2.1 Network Model

Given the tremendous complexity and diversity of WSN applications, the requirements are difficult to clarify in a single network model. This study adopts a general cluster model, in which the sensor nodes are densely but evenly distributed in a two-dimensional terrain.

Figure 1 illustrates the basic structure of the hierarchical WSN model, which is composed of SNs and CHs.

Fig. 1
figure 1

Clustered WSN model with a single base station on the boundary

Full size image

The WSN comprises a large number of low-power and low-cost sensors that are densely deployed in a large physical environment. The whole network is divided into several clusters. CHs are selected among all the SNs through a dynamic clustering approach according to the average transmission cost and residual energy in each CH candidate. In addition, each CH candidate should cover the entire space in its private clustered region and ensure that all the data can be reliably delivered to the BS.

Considering the role assignation in WSN, the main job of SN is to collect raw physical data in the cluster region, with the initial processing of CH election periodically. In succession, the CH in the cluster region delivers the data to the BS in relays, selecting an optimal routing with the least energy cost. In the entire routing procedure, CHs perform complex, intensive tasks and work with other SNs in a collaborative manner.

Some related assumptions in the network model based on the aforesaid CC-HEED are described as follows:

  1. 1.

    The WSN is assumed to be a rectangular geographic district \(R_s\) with a sink (BS) at the centre of the bottom border, and SNs in the network are randomly deployed in \(R_s\).

  2. 2.

    \(R_s\) can be divided into several clusters with a CH in each cluster region.

  3. 3.

    Each cluster region can be further divided into a set of cell-shaped areas with a radius \(R\). A cell node (CN) also exists at the centre (or approximate position) of each cell-shaped area.

  4. 4.

    The sink (BS) periodically sends a request to CHs to upload data samples collected by SNs in each cluster. After receiving the request, CHs will broadcast a data-gathering command to all its members and wait for responses.

2.2 Power Consumption Model

Suppose the distance from a transmitting sensor node \(S\) to a receiving \(D\) is \(x\), then the Friis free-space propagation model [5] demonstrates that the power consumption in data transmitting is proportional to the square of the distance \(x\), which is further described as follows:

$$\begin{aligned} E_{ SD }=x_0 +\varepsilon x^{\alpha } \end{aligned}$$
(1)

Some descriptions and typical values of the related parameters are listed in Table 1.

Table 1 Power consumption model
Full size table

In the light of the network structure, the total power consumption in WSN is simply the sum of the following three parts: (i) the inner-cell energy consumption from SNs to CN in each cell-shaped division, (ii) the inner-cluster energy consumption from CNs to CHs, and (iii) the inter-cluster energy consumption from CHs to BS.

2.3 Lifetime Definitions

Network lifetime can be defined in several ways through different metrics regarding diverse applications.

In some scenarios, such as disastrous weather alert or intruder detection, network quality decreases remarkably after the first sensor node dies. However, in other applications, such as environment monitoring, the loss of a single or few SNs does not dramatically reduce the quality or reliability in WSN. According to the scenarios described above, related metrics on network lifetime and energy efficiency are defined.

  1. 1.

    First node dies (FND), which provides an estimated time for the event when the first node dies in WSN.

  2. 2.

    Last node dies (LND), which demonstrates an estimated time for the event when the last node dies in WSN.

  3. 3.

    Energy Efficiency, which denotes the energy (lifetime) gap between FND and LND, that is, \(\frac{ FND }{ LND }\times 100\,\%\).

3 HEED and Related Networks

Distinguished routing protocols in WSN are studied and summarized in this section. The energy consumption and lifetime distribution can then be analysed and compared vividly with these representative routing protocols:

  1. 1.

    Single-hop protocol: DIRECT

  2. 2.

    Multi-hop protocols:

    1. (1)

      Flat routing: FLOODING, GOSSIPING;

    2. (2)

      Hierarchical routing: LEACH, HEED.

3.1 DIRECT

DIRECT is a simple protocol mainly used for comparison against other WSN protocols. In DIRECT, the sensed data are sent directly to the BS without any intermediate processing or forwarding.

DIRECT requires each node in the network to communicate directly with the BS, assuming that all the nodes are aware of their present locations. Additionally, each node in DIRECT only uses the probable amount of transmission power to reach the BS according to different distances, which cause extreme energy imbalance in the network.

3.2 FLOODING and GOSSIPING

FLOODING is a representation of flat routing protocols with multi-hops, where each node that receives a data packet broadcasts the packet to all the neighbours. This process continues until the data packet arrives at the destination or the maximum number of hops is reached. The vast expanse of data duplication and forwarding makes FLOODING itself a DoS attack [6, 7].

This algorithm is easy to implement but has several drawbacks. The duplicated message sent to the same node in FLOODING will cause serious network implosion and blindness by consuming a large amount of power regardless of energy constraints.

Given the defects of FLOOFING, GOSSIPING provides a significant improvement based on the original algorithm. Instead of broadcasting each data packet to all the neighbours, GOSSIPING only forwards the data packet to a single neighbour, chosen randomly from the present neighbourhood table.

The implosion experienced in FLOODING can be reduced to a certain extend because only one copy of a packet is in transit at a time. However, this reduction in data spreads will cause unpredictable delays in data propagation in the network. Meanwhile, the problem of energy waste because of random transmission still remains unsolved.

3.3 LEACH and HEED

LEACH, regarded as one of the most popular hierarchical routing algorithms, has radical differences from other flat routing protocols.

As shown in Fig. 2, the LEACH routing structure is based on a dynamic cluster approach. LEACH elects CHs among SNs circularly through the received signal strength from BS broadcasting and imposes local CHs as routers to deliver the data to the BS in a single hop.

Fig. 2
figure 2

LEACH network structure

Full size image

In LEACH, the observed region is clustered into several irregular grid-like areas according to a specific CH election approach. CHs are selected periodically by the node location and residual energy. All the SNs are also randomly distributed in the area, continuously sensing the information to CHs. In this way, the overall energy load is allotted equally to all the sensor nodes in the whole network, avoiding the intense energy consumption in certain partial nodes.

However, the lifetime greatly depends on the duration of the cluster election round. In nature, time division multiple access is adopted in LEACH as the scheduling mechanism, which makes LEACH prone to long delays in large sensor networks. In some data-driven applications, where data reports are sent upon request, the duration of the CH election round can range from minutes to hours. LEACH does not have a control mechanism in the CH election, which can lead to an imbalance in CH distribution. Moreover, all the nodes in LEACH, similar to DIRECT, are supposed to overcast the whole observed region, a condition which is not always the case in common WSN applications.

To overcome the one-hop defect in LEACH, HEED is brought out based on a dynamic clustering approach with guaranteed distribution and possibility of communication among CHs. The HEED network structure is illustrated in Fig. 3.

Fig. 3
figure 3

HEED network structure

Full size image

Instead of sending data packets directly to the BS, CHs in HEED that are far from BS will deliver the information to their neighbours by forwarding it to the BS in relays. Thus, the assumption that all nodes should communicate with BS directly and cover the whole region is not necessary in HEED.

However, the CH election mechanism in HEED is different from that in LEACH. CHs are probabilistically elected based on their residual energy and initial rate, namely, \(C_{ prob }\). Each node calculates its probability of becoming a CH as \( CH _{ prob } =C_{ prob } \times (E_{ residual }/E_{ max })\), where \(E_{ residual }\) denotes the estimated residual energy in the present sensor node, and \(E_{ max }\) is the node maximum energy.

In HEED, \( CH _{ prob }\) is not allowed to fall below a specific threshold, otherwise the present node cannot be elected as CH. This restriction gains fast convergence in CH selection.

4 CC-HEED

In this section, a new routing protocol based on HEED, namely, CC-HEED, is proposed. Based on this new protocol, we conceive a hierarchical clustering algorithm for WSN with the goal of energy efficiency. In CC-HEED, the observed region is clustered into several areas; CHs are also elected in each region. The clustering process in CC-HEED, including CH election, is the same as that in HEED. However, distinct differences still exist between these protocols, such as the inner cluster division, which will be discussed in detail in the following section.

As shown in Fig. 4, the inner cluster region in CC-HEED is divided into several cell-shaped areas with a special CN at each cell centre or an approximate position. Compared with HEED, the CN in WSN forms an extra sub-network layer. Hence, raw data collected by SNs are delivered to CN instead of directly to CH; CN will then forward the data to CH in succession. Thus, the data are delivered in relays instead of directly to CH.

Fig. 4
figure 4

CC-HEED network structure in which the inner clusters are divided into cell-shaped regions

Full size image

Similar to HEED, the proposed CC-HEED can be summarised in two phases: (i) inter-cluster process, which initiates the whole network and delivers the data from CHs to BS, and (ii) inner-cluster process, which processes the data between CNs and CHs. The algorithm for CC-HEED is presented in Figs. 5 and 6.

Fig. 5
figure 5

Algorithm of the clustering interval in CC-HEED

Full size image
Fig. 6
figure 6

Algorithm of the operation interval in CC-HEED

Full size image

4.1 Inter-cluster Process

The inter-cluster process in CC-HEED starts with network clustering, including the following steps:

  1. 1.

    \(T_{ cluster }\), clustering process interval, which is the time taken by the clustering protocol to cluster the whole network; and

  2. 2.

    \(T_{ operate }\), operation interval, which is the time between the end of a \(T_{ cluster }\) interval and the start of the successive \(T_{ operate }\) interval. \(T_{ operate }\) should be long than \(T_{ cluster }\) to obtain better network performance.

According to CC-HEED, two parameters, residual energy and average minimum reach-ability power (AMRP), are considered in the CH election.

Residual energy is the primary parameter in CH election. The node with more energy than others has a higher probability of becoming a CH. In CC-HEED, CH candidates with more residual energy are selected as tentative CHs in WSN. However, if residual energy is the only element evaluated in the CH election, it will cause an imbalance in CH distribution because of the primary energy imbalance in SNs. Thus, another parameter, AMRP, is introduced to make the final decision.

AMRP is the mean of the minimum power levels required by all nodes within the cluster range to reach CH. It is described as \( AMRP =\sum \nolimits _{i=0}^M { min \,e_i /M}\), where \( min \,e_i\) denotes the minimum power level required by the node \(i\) in data transmission.

At the beginning, each candidate calculates the AMRP and obtains the list of its neighbours. If the present candidate is a tentative CH with a minimum AMRP, the candidate is declared as the final CH and broadcasts the message to all the other nodes. Then, CHs collect the information from SNs in every cluster region and forward it to the BS in relays through multi-hops.

Ivan et al. [8] proved that this type of data forwarding by a node in the direct line can save energy consumption. This conclusion can also be extended to the applications described in Fig. 7, where node \(A\) is not in the direct line of SD despite calling for a strict precondition of \(d_1^{2}<xy\), where \(d_{1}\) is the distance between nodes \(A\) and \(S\), and y is the distance from node \(A\) to the direct line SD.

Fig. 7
figure 7

Data Transmission from \(S\) to \(D\) via sensor node \(A\)

Full size image

Proof

According to Eq. (1), the power sending data directly from \(S\) to \(D\) is \(E_{S{-}D} =x_0 +x^{2}\), while the energy cost by node A not in the direct line of SD is \(E^{\prime }_{S{-}A{-}D} =2x_0 +d_{1}^{2}+(x-y)^{2}+(d_1^{2}-y^{2})\). Then, \(E_{SD} <E^{\prime }_{ SAD }\) can be obtained in case \(d_1^{2}<xy\), where \(x_{0}\) is omitted in \(x_0 +2d_1^{2}-2xy<0\). \(\square \)

The total transmission power in inter cluster can be calculated as \(\sum \nolimits _{i=1}^k {p_i E_i } +\sum \nolimits _{i=k+1}^n {p_i } (x_0 +d_i^{2})\), where \(p_{i}\) represents the probability of \( SN _{i}\) becoming a CH, \(d_{i}\) describes the direct distance from \( SN _{i}\) to the base station, \(k\) denotes the total number of SNs which call for data forwarding, and \(E_{i}\) is the power consumption in this forwarding. Comparing with LEACH, CC-HEED can save energy of \(\sum \nolimits _{i=1}^k {p_i [} (x_0 +d_i^{2})-E_i]\).

4.2 Inner-cluster Process

After the completion of network clustering in CC-HEED, the remaining sensor nodes in the observed region should collaborate with one another to deliver the sensing data by using some of their neighbours as intermediate nodes to reach the destination.

According to the assumptions in Sect. 2, the whole inner-cluster region can be divided into a set of cell-shaped areas with a CN at the centre (Fig. 8). Instead of sending the data directly to CH, CC-HEED uses CN at each cell centre or an approximate position to aggregate the data and forward it to CH.

Fig. 8
figure 8

Energy consumption in HEED and CC-HEED

Full size image

For the same purpose of further power saving in WSN, the general SN communication ability in the inner cluster in CC-HEED is limited into each cell region, which consumes energy as low as possible in the radio transmission. In this study, each SN is assumed to be capable of transmitting as far as to the CN in the present cell region. In other words, the radius of the cell-shaped area is determined by the transmission range of the SN. Hence, the maximal transmission distance \(R\) can be denoted as the radius of the cluster cell.

Theoretically, we can prove that energy consumption in the inner-cluster process in CC-HEED will be reduced significantly compared with that in HEED.

Proof

Suppose that \(R_1\) is one of the cluster regions in both HEED and CC-HEED. All the SNs \((SN_1 ,SN_2,\ldots , SN_n)\) in CC-HEED are further divided into \(t\) cell-shaped areas \((C_1 ,C_2, \ldots , C_t)\) with radius of \(R\). Thus, energy consumption in CC-HEED can be calculated as

$$\begin{aligned} E_{ CC \text {-} HEED }&= \sum \limits _{i=1}^t {\left( x_0 +d_{ CN _i }^{2}\right) }+E_{ CN _1 } \cdots +E_{ CN _t }\nonumber \\&= \sum \limits _{i=1}^t {\left( x_0 +d_{ CN _i }^{2}\right) } +\sum \limits _{i=1}^{n_1 } {\left( x_0 +d_{ SC _{1i} }^{2}\right) } \cdots +\sum \limits _{i=1}^{n_t } {\left( x_0 +d_{ SC _{ti} }^{2}\right) }, \end{aligned}$$
(2)

where \(d_{ CN _i}\) denotes the distance from \( CN _i\) to CH in \(R_1\), and \(E_{ CN _i}\) represents the energy consumed in cell \(C_{i}\), namely, radio energy from SNs to \( CN _i\). In the extended formulation, \(d_{ SC _{1i}}\) denotes the distance from \( SN _{i}\) to \( CN _{1}\) in cell \(C_{1}\). Analogically, \(d_{ SC _{ti}}\) denotes the distance from \( SN _{i}\) to \( CN _{t}\) in cell \(C_{t}\). \(\square \)

Similarly, the energy consumed in HEED can be concluded as \(E_{ HEED } =\sum \nolimits _{i=1}^n {(x_0 +d_{ SNi }^{2}})\), where \(d_{SNi}\) denotes the distance from \( SN _i\) to CH in \(R_1\).

Given that CNs are selected from SNs in CC-HEED, \(E_{ HEED }\) also contains \(\sum \nolimits _{i=1}^t {(x_0 +d_{ CN _i }^{2})}\). Supposing CH in CC-HEED is selected in cell \(C_{m}\), then \(\sum \nolimits _{i=1}^{n_m } {(x_0 +d_{ SC _{mi} }^{2})}\) is also the same as that in \(E_{ HEED }\) because all the radio distances of the nodes in this region are shorter than the radius \(R\).

To obtain the final conclusion, the remaining items in Eq. (2), namely, energy consumption of the nodes outside the CH cell region, should be further compared.

Obviously, \(d_{ SC _{ti}}\) in CC-HEED is the radio distance from SN to CN in the inner divided region, which is much shorter than the cell radius \(R\), while \(d_{ SNi }\) is the radio distance from SN to CH in HEED, which is much longer than the cell radius \(R\). Hence, the relationship can be described as \(d_{ SC _{ti} } <R<d_{ SNi }\). The conclusion is then proven.

Given that SNs’ distribution is uniform as well as dense, the linear density of SN can be calculated in \(\int _0^{\pi /6} {\rho \frac{\sqrt{3}R}{2\cos \theta }} \;d\theta =\frac{n}{12}\), namely \(\rho =\frac{n}{3\sqrt{3}R\ln 3}\), where \(\rho \) is the linear density of SN, and \(n\) is the total number of SN in this cell region (Fig. 9). Then, the total transmission power in inner cluster can be calculated as \(12\int _0^{\pi /6} {\sum \nolimits _{i=1}^{\rho \sqrt{3}R/2\cos \theta } {[x_0 +\varepsilon (\frac{i}{\rho })^{2}} } ]\;d\theta =x_0 n+1.58R^{3}\rho \varepsilon +2.6\varepsilon R^{2}+0.95R\varepsilon /\rho \).

Fig. 9
figure 9

Energy consumption in CC-HEED

Full size image

5 Simulation Output

Several simulations are carried out to evaluate the performance of CC-HEED. To conduct a comparative study, DIRECT, FLOODING, GOSSIPING, LEACH, and HEED are applied to analyse the lifetime distribution in WSN. This section presents the simulation results and discusses the implications in CC-HEED.

5.1 Setting the Simulation

To evaluate the performance of the proposed algorithm, DIRECT, FLOODING, GOSSIPING, LEACH, HEED, and CC-HEED are implemented in Simulink using the MATLAB language, thus capturing the network behaviours at high fidelity. Furthermore, energy consumptions are modelled in terms of energy dissipated in Eq. (1), with \(x_0 =1{,}000\,\hbox {pJ/bit},\varepsilon =5\times 10^{-8}\,\hbox {J/bit/m}^{2}\), and \(\alpha =2\) in the energy efficiency analysis. CPU calculation costs and data storage are, however, ignored.

The first stage simulation is conducted within a \(1{,}000\,\hbox {m}\times 750\,\hbox {m}\) scene, including 100 random distributed SNs and one BS on the bottom boundary. The whole sensor area is divided into four clusters with four CHs; each SN has an initial energy of 0.5 J with 100 m radio coverage, consuming specific energy in the data transmission according to the energy consumption model.

In the second stage, the radio coverage and the CH numbers are varied from (0, 200] and (0, 8] respectively to study the related impact on cluster-based protocols based on the assumptions listed above.

5.2 Simulation Results and Discussion

The simulation results on network lifetime are shown in Fig. 10. DIRECT seems to obtain better performance compared with other protocols because some nodes are relatively close to the BS, especially when more SNs are distributed near the BS at the bottom boundary in the network. The lifetime in DIRECT will drop dramatically when the BS gets further away from SNs. By contrast, FLOODING is the poorest routing protocol in terms of lifetime because each node will broadcast the message to all its neighbours. GOSSIPING is much more efficient than FLOODING because the sensor nodes deliver the data to only one of its neighbours. However, LEACH is not better than DIRECT because of the unnecessary energy consumption by CHs during the data reception from the nodes already close to BS. Furthermore, CC-HEED gains a more balanced power distribution than HEED in the whole network. This type of distribution, which is attributed to the short data transmission in the divided cell regions, significantly reduces the energy consumption compared with other approaches.

Fig. 10
figure 10

Lifetime distributions according to different routing protocols

Full size image

According to the definition of energy efficiency in Sect. 2, Table 2 shows the energy balance in FLOODING, HEED, and CC-HEED, in which the energy efficiency of HEED is 96.62 % while that of CC-HEED is 99.14 %.

Table 2 Network energy imbalance
Full size table

Figure 11a illustrates the lifetime difference between HEED and CC-HEED with different CH numbers. The network lifetime reaches its climax when the CH number is four because too many CHs will divide the whole cluster region into small pieces that are the same as or even smaller than the cell region. In this situation, nodes in the cell region will not save energy in the network because extra power is severely wasted in data succession among CHs.

Fig. 11
figure 11

Average lifetime in CC-HEED and HEED with a different CHs numbers and b coverage radius

Full size image

The lifetime variations according to coverage radius are presented in Fig. 11b. Radius plays an important role in the lifetime distribution in CC-HEED because it influences the cell division. If the radius is too small to cover enough SNs, cell division will be wasted. However, if the radius is too large to cover all SNs in the cluster region, CC-HEED will return to HEED.

6 Conclusion

Energy efficiency is a crucial point in WSN design. In this paper, a cell-cluster network based on HEED is proposed for energy efficiency, in which the cluster regions are divided into several cell areas. Several simulations are performed to compare the performance of CC-HEED with other notable protocols. Results show that energy consumption in CC-HEED is essentially reduced and power unbalance is effectively improved in WSN.

The power distribution in WSN studied in this paper can be widely used in all kinds of applications, such as emergent data transmissions in meteorological disasters and fire alarm systems in forestry. The new algorithm, CC-HEED, and the final simulation results can also provide evidence for the promotion of advance applications in the future such as wireless vehicle networks.