1 Introduction

Wireless sensor networks (WSNs) consist of a large number of micro sensor nodes that monitor the environment and objects [1, 2]. Sensor nodes are usually deployed in far and inaccessible regions to sense, collect environmental information and transmit the data through wireless links to the base station (BS) for further analysis and processing [3]. Due to the low cost, small size and self-organization of sensors [4], WSNs have been widely used in military, healthcare, environment monitoring, agriculture, etc. [5]. However, the nodes are usually powered by batteries and deployed in harsh environments, it is almost impossible to charge or replace batteries [6]. The key challenge in designing an energy-efficient routing protocol for WSNs is how to save node energy while maintaining the required network performance.

The main aim in WSNs is to control the energy consumption of nodes to prolong the network lifetime [7]. In order to minimize energy consumption, researchers have designed various routing protocols for WSNs. Among them, clustering routing protocols have attracted extensive attention because they can significantly reduce the energy consumption of the network [8]. Clustering routing protocols group sensor nodes into distinct clusters, where each sensor node belongs to one cluster only. In each cluster, a node is elected as the CH, which is responsible for collecting and aggregating the data from the member nodes, and forwarding the data to the BS. Clustering allows most of the sensors (member nodes) to communicate more closely and only a small number of nodes (CHs) need to communicate with a remote BS or other CHs [9]. This approach decreases the energy consumption of the most sensor nodes but increases the additional load of the CHs. The CHs will die prematurely due to excessive energy consumption. Furthermore, clustering protocols commonly use multi-hop communication to transmit information to the BS. The CHs close to the BS consume more energy than other CHs because they must relay a large number of data packets from other CHs [10]. Therefore, compared with other CHs, the CHs near the BS tend to exhaust its energy earlier and cannot provide data relay services for other surviving peripheral nodes. This phenomenon of premature death of some nodes is called the hot spot problem [11].

To address the hot spot problem, Barati et al. [9] proposed a multi-level hierarchical structure to adequately collect and route data in WSNs. Pant et al. [12] proposed a multi-hop routing protocol which uses a grid-based clustering approach to balance the energy consumption of the entire network. However, due to the inconsistent grid number of each rectangle, there will be unnecessary forwarding between layers. Padmanaban et al. [13] proposed an energy-efficient structured clustering algorithm with relay (EESCA-WR) which uses the multiple grid relay approach to reduce the overall energy consumption of the network significantly. However, there is still a problem of excessive load on the nodes close to the BS due to the grids of the same size. Sabor et al. [14] proposed an unequal multi-hop balanced immune clustering protocol to balance the energy consumption of WSNs. Its disadvantage is that it may lead to a large number of message exchanges through the network to determine the cluster size and exchange current energy status information. Therefore, due to the high energy consumption and load imbalance of existing schemes, it is necessary to develop an effective load balancing protocol for WSNs to prevent the premature death of nodes  and prolong the network lifetime.

Aiming at the aforementioned issues, this paper proposed an uneven annulus sector grid-based energy-efficient multi-hop routing protocol (UASGRP). Our idea is to use an uneven clustering mechanism to adjust the cluster size according to the distance from the grids to the BS to reduce the energy consumption of nodes. An uneven gradient annulus sector grid division approach is introduced to divide the network area into several clusters, which alleviates the hot spot problem and achieves better energy balance. Furthermore, CM nodes are used to undertake inter-cluster communication to lighten the load of CHs. A nearest interlayer routing algorithm is proposed to construct data transmission routes to reduce the energy consumption during routing process. In order to determine the efficiency of the proposed UASGRP, this paper compares its performance with existing routing algorithms and validates the potential of the proposed scheme. The major contributions of this paper can be summarized as follows:

1. An uneven gradient annulus sector grid division approach is proposed, which divides the network area into grids with unequal sizes to form clusters. The clusters close to the BS is smaller, and the clusters far away from the BS is larger. This cluster distribution can achieve load balancing and alleviate the hot spot problem.

2. A communication scheme based on bifunctional nodes is used to reduce the load of CHs. A novel weighting mechanism is introduced to select the CM nodes and the CHs, which considers both residual energy and distance. Therefore, the energy consumption of nodes within the clusters is minimized.

3. A nearest interlayer routing algorithm is proposed to construct a multi-hop data transmission route. The algorithm considers both the distance between CM nodes and the transmission range to reduce unnecessary data forwarding. Theoretical analysis is given to prove that the algorithm can effectively reduce the energy consumption of relay transmission.

The rest of the paper is organized as follows: In Sect. 2, the related work is presented. In Sect. 3, network model, energy consumption model and specific model parameters are described. Section 4 introduces the novel idea and implementation process of UASGRP, and gives corresponding proofs through an energy consumption estimation approach. Section 5 analyzes the performance of the proposed protocol through comparative experiments with several other grid-based clustering protocols. Section 6 is the conclusion of this paper.

2 Related work

Due to the limited energy of sensor nodes in WSNs, designing energy-efficient routing protocols for WSNs has been widely concerned by researchers. In recent years, a variety of routing protocols have been proposed and investigated. Low Energy Adaptive Clustering Hierarchy (LEACH) [15] is one of the earliest clustering routing protocols. It groups sensor nodes into different clusters and divides the network operation period into rounds. In each round, each cluster has a CH which is responsible for collecting and aggregating the data from the member nodes in the cluster. LEACH can distribute the energy load among the sensors in the network through adaptive clusters and rotating cluster heads. Thus, the network lifetime is prolonged dramatically. However, the CH election based on  probabilistic model and the single-hop communication will result in unreasonable clustering and premature death of some nodes.

In order to solve the issues of LEACH, researchers extended the work of LEACH to improve the CH election and cluster formation. LEACH-centralized (LEACH-C) [16] adopts a centralized clustering algorithm and the same steady-state protocol as LEACH. After receiving the information (ID, location, residual energy, etc.) of all nodes, the BS adopts the simulated annealing (SA) algorithm to find k optimal clusters, which ensures the balanced cluster formation and the uniform load distribution amongst the sensor nodes. LEACH-C tends to minimize the total sum of squared distances between all the non-CH nodes and the closest CH. Thus, the amount of energy for intra-cluster data transmission is minimum. Aziz et al. [17] proposed a hybrid clustering algorithm based on k-means clustering algorithm and LEACH, where balanced clusters are generated by k-means and CHs are selected by LEACH. This hybrid algorithm outperforms LEACH in terms of the energy consumption and the network lifetime. However, both LEACH-C and the hybrid algorithm do not consider the amount of energy for the CHs to transmit the data to the BS. Therefore, they are not applicable to large-scale WSNs.

Finding optimal clusters and routing paths is a NP-hard problem, which can be regard as an optimization problem. Many researchers tried to adopt some algorithms to solve the optimization problem in WSNs [18,19,20,21]. Ruan et al. [22] proposed a PSO-based uneven Dynamic Clustering Routing Protocol (PUDCRP) for WSNs, which achieves the maximum coverage across the network and makes the number of nodes in each cluster match its size. The authors introduce an improved Particle Swarm Optimization (PSO) algorithm to divide the network area into circles with unequal sizes based on the distribution of nodes. In CH election, they consider residual energy, the degree of neighbor nodes and the distance between nodes and the BS to minimize the intra-cluster energy consumption. However, due to the frequent re-clustering, the energy consumption of the nodes will increase in the phase of cluster formation and the CH election.

In [23], the authors proposed Multipath Routing through the Firefly Algorithm and Fuzzy Logic (MRFAFL) in WSNs. MRFAFL uses the firefly algorithm to cluster the nodes and build multipath routing between CHs based on fuzzy logic. Besides, MRFAFL creates primary path and backup path to deal with the failure of routing paths. Thus, the multipath routing has great performance in end-to-end delay and packet loss rate. Zhu et al. [6] proposed an Improved Soft-k-means (IS-k-means) clustering algorithm for balancing the energy consumption in WSNs. The authors adopt the idea of clustering by fast search and find of density peaks and kernel density estimation to improve the selection of the initial cluster centers. To balance the number of nodes per cluster and the energy consumption within clusters, the authors consider the membership probabilities at the boundary of clusters to reassign member nodes and adopt multi-cluster heads. However, the combination of several technologies for optimal results increases the computational complexity and time complexity.

Grid-based clustering protocols divide the network into different areas (called grids) according to the geographical location of nodes, where all the nodes in the same grid form a cluster. This scheme can simplify the cluster formation and improve the energy efficiency of the network. Some protocols divide the entire network area into square grids with equal size. In [24], a set of sensor nodes called local aggregations (LAs) are elected in each grid and then master aggregations (MAs) are elected from all LAs. The authors use a hierarchical model that utilizes data aggregation and in-network processing at two levels of the network hierarchy. In Grid Based Fault Tolerant Clustering and Routing Algorithm (GFTCRA) [25], the node with the smallest sum of the distance to other nodes in the same grid and the residual energy greater than the energy threshold will be elected as the CH. This approach ensures that the energy consumption of CHs in each grid is the minimum. In [26], each grid is assigned a CH and other nodes can choose to be cluster member nodes or independent nodes. CHs and independent nodes cover the whole network through multi-hop transmission, which can balance the energy consumption of nodes to a certain extent. However, these protocols do not consider the hot spot problem. In EESCA-WR [13], the grids have a single grid leader (GL) and multiple grid relays (GRs). The GLs are rotated in the right intervals and each GR only forwards the data from a specific grid. The policy of allotting dedicated relay nodes in each grid makes it better for homogeneous and heterogeneous WSNs. However, there is still a problem of excessive load on the nodes close to the BS due to the grids of the same size.

Multi-hop routing approaches can reduce energy consumption and improve scalability in WSNs. However, the CHs close to the BS undertake more data forwarding tasks and die prematurely, which will result in the hot spot problem and network partitions. Soro and Heinzelman [27] proposed an Unequal Clustering Size (UCS) model for network organization, where the network topology is assumed as a two-layer concentric ring surrounding the BS. In UCS, some super nodes take on the CH role to control network operation and the CHs in the inner ring forward data from the outer ring. This model achieves more uniform energy dissipation among the CHs. However, the locations of super nodes are calculated in advance, which is not applicable to homogeneous networks where sensor nodes are randomly distributed. Unequal Cluster-based Routing (UCR) protocol [28] selects some nodes as candidate CHs with a certain probability. The candidate CHs adopt unequal competition ranges to perform partial competition. The result is that the clusters closer to the BS are expected to have smaller sizes, thus the CHs will consume lower energy during the intra-cluster data processing, and can preserve more energy for the inter-cluster relay traffic. UCR considers the tradeoff between the energy cost of relay links and the energy of relay nodes. Unequal Clustering and Connected Graph Routing Algorithm (UCCGRA) [29] considers the energy consumption of transmission as a key factor. This protocol uses the voting mechanism to elect CHs and the connected graph theory to construct data transmission paths between clusters. This work highlights the concept of balancing the energy for inter-cluster and intra-cluster communication. However, these schemes mentioned above all use dynamic virtual topologies with variable cluster sizes, which will incur higher energy consumption.

Uneven grid-based clustering protocols with a fixed and simple architecture can achieve the goal of balancing node energy consumption by constructing clusters with unequal sizes. Energy Efficient and Balanced Cluster Data Aggregation algorithm (EEBCDA) [30] and multi-hop EEBCDA [12] divide the network area into multiple rectangles of equal size. Each rectangle is divided into multiple rectangular grids of unequal sizes and the grid number in each rectangle is different. The number of nodes participating in the rotation of CHs is adjusted according to the characteristics of energy consumption in different regions. This approach significantly balances the energy consumption of nodes and prolongs the network lifetime. However, the difference in the number of grids in each rectangle may cause unnecessary forwarding between layers.

In cluster-based routing protocols, CHs bear most of the load in each round. The communication mechanism based on bifunctional nodes can alleviate the burden of CHs and balance the energy consumption. In this scheme, each cluster contains a CH and a CM node. The CH is responsible for receiving and aggregating the data from the member nodes and then transmitting the data to the CM node in the cluster. The CM nodes perform data transmission between clusters to share the burden of CHs. In [31], the authors also adopt the approach of dividing the network area into uneven rectangular grids. Moreover, they comprehensively consider the location of nodes, the distance to the BS and the communication consumption between nodes to select the appropriate next hop. In Annulus Sector Grid-based Routing Protocol (ASGRP) [32], the authors propose an arithmetic annulus sector grid division approach, which ensures that the range from clusters in the same ring to the BS is the same. This approach balances the energy consumption since the nodes in a grid consume roughly the same amount of energy during data transmission. However, each ring evenly divided into grids will cause that the number of grids close to the BS is large and far away from the BS is small in a square network area. And the changes of the grid sizes at different levels are not even enough, which causes much unnecessary energy consumption.

3 Network and energy model

3.1 Network model

The assumptions of the network used in this work are listed as follows:

  1. 1.

    There are N sensor nodes randomly deployed in a square network area of size M × M.

  2. 2.

    The unique stationary BS (or sink) is located at the midpoint of the boundary of the square area and does not have any energy constraint.

  3. 3.

    All sensor nodes are homogeneous and have the same initial energy, transmission range and transmission rate.

  4. 4.

    All sensor nodes are aware of their own locations through GPS or other localization mechanisms and residual energy.

  5. 5.

    All sensor nodes can adjust their energy consumption based on the distance to the receiver.

  6. 6.

    Each node has a unique ID and can be represented as i (its ID).

  7. 7.

    Communication channel is reliable and error free.

  8. 8.

    All sensor nodes are stationary after deployment.

3.2 Energy model

In this paper, the first order radio model [15] is used for calculating the energy consumption as shown in Fig. 1. In this model, \({E}_{{T}_{x}}\) represents the energy consumed for sending data, which is the sum of the energy consumed by the transmitting circuit and the power amplifier. \({E}_{{R}_{x}}\) denotes the energy consumed for receiving data, which is the energy consumed by the receiving circuit. \({E}_{Amp}\) denotes the energy consumed by the power amplifier, which is related to the distance between the sending node and the receiving node. The energy consumed by two nodes with a distance of d to transmit and receive k bits data can be calculated by Eq. (1) and Eq. (2).

Fig. 1
figure 1

Energy consumption model

Full size image
$${E}_{{T}_{x}}\left(k,d\right)={E}_{TE}+{E}_{Amp}=\left\{\begin{array}{c}k\times {E}_{elec}+k\times {\varepsilon }_{fs}\times {d}^{2}, d<{d}_{0}\\ k\times {E}_{elec}+k\times {\varepsilon }_{mp}\times {d}^{4}, d\ge {d}_{0}\end{array}\right.$$
(1)
$${E}_{{R}_{x}}\left(k\right)={E}_{RE}=k\times {E}_{elec}$$
(2)

where \({E}_{elec} \left(50 nJ\cdot {bit}^{-1}\right)\) is the dissipated energy per bit in both transmitting circuit and the receiving circuit. \({\varepsilon }_{fs}\) and \({\varepsilon }_{mp}\) are amplifier coefficients of free-space model and multi-path fading model respectively. The threshold distance d0 is calculated by Eq. (3).

$${d}_{0}=\sqrt{{\varepsilon }_{fs}/{\varepsilon }_{mp}}$$
(3)

When d < d0, the free-space model is used to calculate the energy consumption of nodes and the amplifier parameter is \({\varepsilon }_{fs} (10 pJ\cdot {bit}^{-1}\cdot {m}^{-2})\). When d ≥ d0, the multi-path fading model is used and the amplifier parameter is \({\varepsilon }_{mp} (0.0013 pJ\cdot {bit}^{-1}\cdot {m}^{-4})\). d0 (87.7 m) is the threshold distance of wireless communication. In this paper, the maximum transmission distance is specified as d0, which ensures that the nodes in the same cluster of the uneven annulus sector grid division approach are all within the same transmission range.

The energy consumed by CHs to aggregate m packets which respectively have k1, k2, k3, ……, km bits can be calculated as follows:

$${E}_{DA}\left(k,m\right)={\sum }_{j=1}^{m}{E}_{agg}\times {k}_{j}$$
(4)

In Eq. (4), \({E}_{agg} (5 nJ\cdot {bit}^{-1})\) is the energy consumed for aggregating 1-bit data.

Based on Eq. (1) and Eq. (2), \({E}_{TE}={E}_{RE}= k\times {E}_{elec}\), when d < d0, \({E}_{Amp}=k\times {\varepsilon }_{fs}\times {d}^{2}\). When the data packet length is determined, we assume \(k\times {E}_{elec}=\mathrm{e}\). Let \({E}_{Amp}=e\), then d = 70.7(m). When d = d0, \({E}_{Amp}=1.54e\) and when d = d0/2, \({E}_{Amp}=0.38e\). The energy consumption for aggregating a data packet is \(k\times {E}_{agg}=0.1\mathrm{e}\).

4 UASGRP routing protocol

UASGRP divides the entire network lifetime into operation rounds. Each round includes a set-up phase and a steady-state phase. In addition, at the very beginning of the round operation, there is an initialization phase during which network parameter initialization and grid division are performed. The operation process of UASGRP is as shown in Fig. 2.

Fig. 2
figure 2

UASGRP protocol process

Full size image

4.1 Protocol initialization

4.1.1 Node position

In the initialization phase, the BS first broadcasts its own position to all sensor nodes in the network. After receiving the information from the BS, each node uses the coordinate formulas to calculate the distance between itself and the BS, as well as the arc angle based on its own position and the BS position. The specific formulas are as follows:

$${d}_{i}=\sqrt{{\left({x}_{i}-{x}_{BS}\right)}^{2}+{\left({y}_{i}+{y}_{BS}\right)}^{2}}$$
(5)
$${\theta }_{i}=\mathrm{arccos}(({x}_{i}-{x}_{BS})/{d}_{i})$$
(6)

where di is the Euclidean distance between node i and the BS. The position of node i is (xi, yi) (the lower left corner is the origin of the coordinate system as shown in Fig. 3) and the position of the BS is (xBS, yBS). θi is the arc angle formed by the connected line from the node to the BS and the boundary where the BS is located.

Fig. 3
figure 3

The distance and arc angle of a node

Full size image

4.1.2 Grid-division

Grid-based clustering protocols should ensure that CHs are distributed in the network area as reasonably as possible to achieve load balancing. In order to find a better way to improve the energy balance of the network, we must first know the energy consumption of nodes under various approaches and parameters. It can be seen from Sect. 3.2 that when d = d0, \({\mathrm{E}}_{Amp}=1.54e\), and when d = d0/2, \({E}_{Amp}=0.38e\). When the distance d between two nodes is small, the energy consumption of the sending node and the receiving node is relatively close. To prolong the network lifetime, the transmission distance of nodes should be controlled within a reasonable range to reduce unnecessary energy consumption.

In multi-hop routing protocols, the CHs close to the BS undertake more data forwarding tasks, which causes these nodes to die prematurely due to higher energy consumption. To solve this problem, an effective solution is to make the clusters closer to the BS have smaller sizes. Small clusters close to the BS have fewer nodes and shorter transmission distances to the BS. This scheme can compensate the energy consumption of CHs near the BS by forwarding data from a farther CH.

Lemma 1: Assuming that only the energy consumed for collecting the data from all the nodes in a cluster is considered. If the cluster close to the BS is small and the cluster far away from the BS is large, then the larger the cluster, the more the average energy consumption of nodes in each cluster per round, and the smaller the cluster, the less the average energy consumption.

Proof: In a cluster that consists of n nodes, the energy consumed by non-CH nodes and CHs in each round can be calculated by Eqs. (7) and (8) respectively.

$${E}_{non-CH}=k\times {E}_{elec}+k\times {\varepsilon }_{fs}\times {d}_{i-CH}^{2}=e+{d}_{i-CH}^{2}$$
(7)
$$\begin{aligned}{E}_{CH}&=\left(n-1\right)\times k\times {E}_{elec}+n\times k\times {E}_{agg}+k\times {E}_{elec}\\&+k\times {\varepsilon }_{fs}\times {d}_{NH}^{2}=1.1ne+k\times {\varepsilon }_{fs}\times {d}_{NH}^{2}\end{aligned}$$
(8)

where di-CH is the distance from node i to the CH in its cluster, and dNH is the distance from the CH to the next hop.

In each round, the total energy consumed by the entire cluster and by each node can be calculated by Eqs. (9) and (10).

$$\begin{aligned}{E}_{cluster}&=\left(n-1\right){\times E}_{non-CH}+{E}_{CH}=\left(2.1n-1\right)e\\&+{\sum }_{i=1}^{n-1}k\times {\varepsilon }_{fs}\times {d}_{i-CH}^{2}+k\times {\varepsilon }_{fs}\times {d}_{NH}^{2}\end{aligned}$$
(9)
$$\begin{aligned}\overline{{E }_{i}}&={E}_{cluster}/n=2.1e-\frac{1}{n}e\\&+({\sum }_{i=1}^{n-1}k\times {\varepsilon }_{fs}\times {d}_{i-CH}^{2}+k\times {\varepsilon }_{fs}\times {d}_{NH}^{2})/n\end{aligned}$$
(10)

In the cluster, the average energy consumed by each node in each round is between 2e-3.54e. The larger the cluster, the larger \({d}_{i-CH}\), and the more energy consumed by each node on average.

The energy consumed by CHs to receive and forward the data of other CHs is not considered above. In fact, a CH close to the BS needs to receive and forward more data from the farther CHs, which requires additional energy consumption. Therefore, the scheme that the clusters closer to the BS have smaller sizes can balance the energy consumption.

Rectangular grid-based clustering schemes [28, 29] make the clusters closer to the BS have smaller sizes. Hence their performance is better than that of DAEA and GFTCRA based on square grid clustering. However, rectangular grid-based clustering has the problem of unbalanced energy consumption of grids at the same level. To solve this problem, ASGRP proposed an arithmetic annulus sector grid clustering scheme to further balance the energy consumption. Experimental results show that the scheme is better than rectangular grid-based clustering. However, the arithmetic annulus sector grid clustering approach has the problem that there are too many clusters close to the BS and few clusters far away from the BS. In response to this problem, this paper proposes an uneven arithmetic annulus sector grid-based clustering approach to form a different number of clusters at each layer, which can better balance energy consumption.

The uneven arithmetic annulus sector grid-based clustering approach divides the network area into annulus sector grids. It takes the BS as the center of the circle to divide the square network area into L rings whose generatrix length (the external diameter minus the internal diameter) increases by an arithmetic sequence. From the BS to the outside, the grids belong to different layers. The layer closest to the BS is called the first layer (its layer number is 1), the next layer is the second layer, and so on. On the other hand, to better balance the energy consumption of nodes in the same layer, the number of grids in each layer is proportional to the layer number where the grid is located. The schematic diagram of annulus sector grids layout is as shown in Fig. 4. The number of grids in the lth layer (hl) can be calculated by Eq. (11).

Fig. 4
figure 4

Schematic diagram of annulus sector grids layout

Full size image
$${h}_{l}=2\times l,(1\le l\le L)$$
(11)

The grids of the same layer are numbered from left to right from 1 to hl. Each grid can be represented by ID (hk, l) (\(1\le k\le l\)). Compared with the rectangular grid approach, the annulus sector grid approach can ensure that the nodes in the grids of the same layer are within the same distance from the BS. Thus, their energy consumption is approximate during data transmission, which means more balanced load of nodes.

Assuming that the generatrix length of the first layer is d1. Starting from the first layer, we use the arithmetic formula to determine the generatrix length of each layer. If the network is divided into L layers, the generatrix length dl of the lth layer can be calculated by Eq. (12).

$${d}_{l}={d}_{1}+(l-1)\times \Delta d$$
(12)

where \(1\le l\le L\) and \({d}_{l}<{d}_{0}\). d1 and ∆d are constants and need to be determined in advance.

In clustering routing protocols, the appropriate number of clusters is crucial to the effectiveness of clustering approaches. If there are too many clusters, it will increase the amount of the data to be forwarded and the load of nodes close to the BS. If the cluster number is too small, it will increase the load of CHs, which causes CHs to consume more energy and die prematurely. Hence, when dividing grids, the number of grids should be changed according to the number of nodes, the network area range and other factors. In other words, the parameter values for dividing grids are not the same in different network scenarios. This paper estimates the corresponding grid parameters based on the energy consumption of nodes in different layers. Then we obtain the values of L, \(\Delta d\) and d1 in different network scenarios through experiments, as shown in Table 1.

Table 1 Parameters in different network areas
Full size table

4.2 Set-up phase

The load of CHs in a clustering routing protocol is heavy. A CH is not only responsible for data collection within the cluster, but also for data forwarding between clusters. In UASGRP, we introduce CM nodes to undertake inter-cluster data transmission, while CHs are only responsible for data collection and data aggregation in their own clusters. This communication scheme based on bifunctional nodes can reduce the load of CHs and effectively balance the energy consumption.

The purpose of the set-up phase is to select CHs and CM nodes. In this phase, CM nodes are first elected in each cluster. Both the residual energy and the distance from nodes to the BS are considered. The weight Wi of node i is used to determine whether it is the CM node in its cluster or not in current round. Wi is calculated as follows:

$${W}_{i}=\alpha \times \frac{{E}_{i}}{\overline{E}(h,l)}+(1-\alpha )\times \frac{\overline{d}(h,l)}{{d}_{i}}$$
(13)

where Ei is the residual energy of node i. α (0 < α \(\le\) 1) is a weight coefficient and α = 0.1 ∗ j (0 < j ≤ 10; j ∈ N). \(\overline{E}(h,l)\) is the average residual energy of all nodes in grid (h,l) (1 < l ≤ L). \(\overline{d}(h,l)\) is the average distance between the nodes and the BS. The distribution of CM nodes and CHs is shown in Fig. 5.

Fig. 5
figure 5

The schematic diagram of CH nodes and CM nodes distribution

Full size image

In the initialization phase, a node obtains the information (node ID, position coordinates, residual energy, weight, etc.) of all neighbor nodes in the same grid through the neighbor discovery mechanism, and stores the information in the neighbor node information table. In each round, each node needs to calculate the weight according to the above weight formula. In each cluster, the node with the largest weight is elected to be the CM node and the node with the most residual energy to be the CH. Subsequently, CHs broadcast TDMA time slots to other nodes in the cluster to establish a mechanism for data transmission to the CHs in turn. In each round starting from the second round, when an ordinary node sends data to the CH, it adds its own residual energy and weight to the end of the data packet. This approach can reduce control messages.

4.3 Steady-state phase

Before sending data to the BS, energy-efficient transmission routes from sensor nodes to the BS must first be established. This paper proposes a nearest interlayer routing algorithm to address this issue. According to the distance between the BS and the nodes and the characteristics of the routing algorithm, we divide grids into inner grids and outer grids in the initialization phase. Among them, the grids of the first and second layers are inner grids and other grids are outer grids. The data transmission algorithms used in the inner grids and the outer grids are different.

The distance between all the nodes in inner grids and the BS is less than d0. Hence, they transmit data to the BS directly. CM nodes in outer grids adopt a multi-hop communication approach and perform data transmission according to the path constructed by the nearest interlayer routing algorithm. This algorithm tries to ensure that the distance between the two CM nodes is less than d0. Compared with the nearest neighbor routing algorithm adopted by ASGRP (a CM node selects the nearest CM node in the next grid for data transmission), the nearest interlayer routing algorithm is more efficient because it reduces unnecessary energy consumption. The diagram of the routing process of different nodes is shown in Fig. 6.

Fig. 6
figure 6

Routing process diagram

Full size image

In the steady-state phase, different nodes have different transmission strategies. According to the grid where a node is located and the distance between the node and the BS, following different routing strategies can be selected for data transmission:

  • Case 1: An ordinary node in inner grids directly transmits its data to the BS.

  • Case 2: An ordinary node in outer grids transmits its data to the CH.

  • Case 3: A CM node in inner grids forwards the data received from the CM nodes of the outer grids to the BS.

  • Case 4: A CH in outer grids aggregates the data received from other ordinary nodes and transmits it to the CM node in the grid.

  • Case 5: A CM node in outer grids forwards the data from the CH in the grid and the data from CM nodes in the upper grids (with a larger grid number) to the next hop CM node selected by the nearest interlayer routing algorithm.

The nearest interlayer routing algorithm is illustrated in algorithm 1. The idea of this algorithm is that CM node i first finds the nearest CM node j in the interlayer grid (for example, the CM node in the third layer looks for the CM node in the first layer). If the distance between the two CM nodes is less than d0, CM node j will be the next hop of CM node i. Otherwise CM node i finds the nearest CM node k in the next layer to be the next hop. In theory, this approach can reduce the communication traffic of CM nodes close to the BS by half in the best case. In order to prove the effectiveness of the routing algorithm, the lemmas and proofs are given below according to the energy model.

figure d

Lemma 2: The direct transmission scheme in which nodes in inner grids transmit data to the BS directly can save more energy than the clustering scheme.

Proof: The energy consumption of the nodes in an inner grid with n nodes transmitting data directly to the BS can be calculated by Eq. (14).

$${E}_{inner-grid}=n\times {E}_{i-con}=ne+{\sum }_{i=1}^{n}k\times {\varepsilon }_{fs}\times {d}_{i-BS}^{2}$$
(14)

where \({E}_{i-con}\) is the energy consumed by node i, and \({d}_{i-BS}\) is the distance from node i to the BS.

The average energy consumed by the nodes in the grid of the first layer in each round is between e-1.38e, and the average energy consumed by the nodes in the grid of the second layer in each round is between 1.38e-2.54e. It can be known from lemma 1 that in the clustering scheme, the energy consumed by the nodes in each cluster in each round is between 2e-3.54e. It can be seen that the energy consumption of the direct transmission scheme is less than that of the clustering scheme. Therefore, in this paper, the nodes in the inner grids use the direct transmission scheme to transmit data to the BS to obtain better energy efficiency.

Lemma 3: When the transmission distance is smaller than d0, the nearest interlayer routing algorithm saves more energy than the nearest neighbor routing algorithm.

Proof: As shown in Fig. 7, assuming that the dashed path and the solid path respectively represent the paths obtained by the nearest neighbor layer routing algorithm and the nearest interlayer routing algorithm. Each CM node receives data from the CM node in the upper layer (with a larger ID) and forwards it to the CM node in the lower layer. The parameters are shown in Fig. 7.

Fig. 7
figure 7

The path obtained by two routing algorithms

Full size image

In the dashed path, the energy consumption of each node can be calculated as follows:

$$\begin{aligned}{E}_{4}&=k\times {E}_{elec}+k\times {\varepsilon }_{fs}\times {d}_{4}^{2}\\&=\mathrm{e}+k\times {\varepsilon }_{fs}\times {d}_{4}^{2} \in (e,2.54e)\end{aligned}$$
$$\begin{aligned}{E}_{3}&=k\times {E}_{elec}+2k\times {E}_{elec}+2k\times {\varepsilon }_{fs}\times {d}_{3}^{2}\\&=3\mathrm{e}+2k\times {\varepsilon }_{fs}\times {d}_{3}^{2} \in (3e,6.08e)\end{aligned}$$
$$\begin{aligned}{E}_{2}&=2k\times {E}_{elec}+3k\times {E}_{elec}+3k\times {\varepsilon }_{fs}\times {d}_{2}^{2}\\&=5\mathrm{e}+3k\times {\varepsilon }_{fs}\times {d}_{2}^{2} \in (5e,9.62e)\end{aligned}$$
$$\begin{aligned}{E}_{1}&=3k\times {E}_{elec}+4k\times {E}_{elec}+4k\times {\varepsilon }_{fs}\times {d}_{1}^{2}\\&=7e+4k\times {\varepsilon }_{fs}\times {d}_{1}^{2} \in (7e,13.16e)\end{aligned}$$

The total energy consumption of all the nodes is as follows:

$$\begin{aligned}\mathrm{E}&={{E}_{1}+E}_{2}+{{E}_{3}+E}_{4}\\&=16e+10k\times {\varepsilon }_{fs}\times {(d}_{1}^{2}+{d}_{2}^{2}+{d}_{3}^{2}+{d}_{4}^{2}) \in (16e,31.4e)\end{aligned}$$

In the solid path, the energy consumption of each node can be calculated as follows:

$$\begin{aligned}{E}_{4}&=k\times {E}_{elec}+k\times {\varepsilon }_{fs}\times {d}_{7}^{2}\\&=\mathrm{e}+k\times {\varepsilon }_{fs}\times {d}_{7}^{2} \in (e,2.54e)\end{aligned}$$
$$\begin{aligned}{E}_{3}&=k\times {E}_{elec}+k\times {\varepsilon }_{fs}\times {d}_{6}^{2}\\&=\mathrm{e}+k\times {\varepsilon }_{fs}\times {d}_{6}^{2} \in (e,2.54e)\end{aligned}$$
$$\begin{aligned}{E}_{2}&=k\times {E}_{elec}+2k\times {E}_{elec}+2k\times {\varepsilon }_{fs}\times {d}_{5}^{2}\\&=3\mathrm{e}+2k\times {\varepsilon }_{fs}\times {d}_{5}^{2} \in (3e,6.08e)\end{aligned}$$
$$\begin{aligned}{E}_{1}&=k\times {E}_{elec}+2k\times {E}_{elec}+2k\times {\varepsilon }_{fs}\times {d}_{1}^{2}\\&=3\mathrm{e}+2k\times {\varepsilon }_{fs}\times {d}_{1}^{2} \in (3e,6.08e)\end{aligned}$$

The total energy consumption of all the nodes is as follows:

$$\begin{aligned}\mathrm{E}&={{E}_{1}+E}_{2}+{{E}_{3}+E}_{4}\\&=8e+k\times {\varepsilon }_{fs}\times {(2d}_{1}^{2}+2{d}_{5}^{2}+{d}_{6}^{2}+{d}_{7}^{2}) \in (8e,17.24e)\end{aligned}$$

Comparing the energy consumption of each CM node in the two schemes, it can be clearly seen that the energy consumption of the CM nodes with the nearest interlayer routing algorithm is significantly lower than that of the CM nodes with the nearest neighbor routing algorithm.

4.4 Complexity analysis

As Sect. 3.1 supposed, there are N nodes and K grids in the network area. In K grids, there are 6 inner grids where nodes adopt the intra-cluster election strategy. In the initialization phase, all nodes broadcast their own state information, and there are N messages in total. The proposed algorithm needs O(N) operations, and O(N) memory units are required to store neighbor information in total. In the set-up phase, K CM nodes broadcast the messages that they are elected as CM nodes and K-6 CM nodes send messages to elect CHs. Then K-6 CHs broadcast the messages that they are elected as CHs. There are 3 K-12 messages in total. N-2 K + 6 nodes send messages to CHs and there are N-2 K + 6 messages in total. Therefore, the total number of messages in the control algorithm is 2 N + K-6. Besides, the routing algorithm needs O(2 K) operations at most to find next hop. Thus, the time complexity of the UASGRP is O(N) and the total storage requirements is O(N) memory units.

5 Simulation and results

5.1 Simulation parameters

Simulations are performed in MATLAB to evaluate the proposed protocol. In order to make the comparison results more reliable, it is necessary to make the compared protocols run in the same network environment and use the same network parameters. Hence, we choose two different network scenarios that are the same as many literatures. The parameters of the network areas are preset. The simulated network areas are 200 m \(\times\) 200 m and 400 \(\times\) 400 m respectively. The grid parameters are set according to the data in Sect. 4.1.2. The simulation parameters of the network are shown in Table 2.

Table 2 Simulation parameters
Full size table

5.2 Result analyzation

To evaluate the proposed protocol, we compare the first node death time and network lifetime of UASGRP with GFTCRA, multi-hop EEBCDA, EESCA-WR and ASGRP in different network scenarios. In this paper, the number of running rounds when 80% of the nodes in the network area die is regarded as the network lifetime. At this time, the data obtained by the BS is distorted seriously and the network is considered to be invalid. To facilitate the analysis below, Table 3 summarizes the characteristics of the five protocols.

Table 3 Characteristics of 5 protocols
Full size table

In order to make the experimental results more objective, we simulated different distributions of nodes and performed multiple experiments. The round number of the first node death (FND) and the last node death (LND) of the five protocols in different network scenarios are shown in Tables 4 and 5.

Table 4 The average rounds of UASGRP in the 200 m × 200 m network area
Full size table
Table 5 The average rounds of UASGRP in the 400 m × 400 m network area
Full size table

According to Tables 4 and 5, the UASGRP protocol runs more rounds than the other four protocols under the same network conditions. In the 200 m × 200 m network, compared with GFTCRA, Multi-hop EEBCDA, EESCA-WR and ASGRP, the time of the FND in UASGRP is delayed by 21.7%, 16.6%, 15.7% and 14.3%, and the network lifetime of UASGRP is increased by 31.4%, 25.2%, 18.9% and 9.6% respectively. In the 400 m × 400 m network, the time of the FND in UASGRP is delayed by 472.4%, 263.4%, 113.3% and 57.5%, and the network lifetime is extended by 33.0%, 15.6%, 12.7% and 3.4% respectively.

GFTCRA, Multi-hop EEBCDA and EESCA-WR all adopt rectangular grid clustering approaches. The CHs on both sides of the network area need to transmit data to the CHs in the grids closer to the BS, which increases the load of these relay nodes. Besides, in GFTCRA, the node with the smallest sum of distances from other nodes in the same cluster and enough residual energy (more than the energy threshold) will be elected as a CH. The CHs will be changed until their energy is smaller than the threshold, which will cause these nodes to die prematurely. Thus, the occurrence of FND in GFTCRA is much earlier. EESCA-WR adopts the assigned relay nodes to forward data between clusters which shares the load of CHs and balance energy consumption. Hence, it has better performance than Multi-hop EEBCDA. The performance of FND and LND of ASGRP and UASGRP is better than that of the other three protocols because ASGRP and UASGRP both use annulus sector grid clustering approaches. However, the grid division of ASGRP is not reasonable enough and some nodes whose distance to the BS is less than d0 still forward data to inner nodes, which increases the energy consumption of inner nodes and leads to the early appearance of the first failed node. UASGRP improves the grid clustering approach to make the distribution of CHs more uniform and employs a nearest interlayer routing algorithm to reduce unnecessary energy consumption, which indicates that the energy consumption of nodes in UASGRP is more balanced than that of ASGRP. Therefore, the performance of UASGRP is better than that of ASGRP and the other three protocols.

In addition, the experiments also obtained the number of alive nodes during the operation of GFTCRA, Multi-hop EEBCDA, EESCA-WR, ASGRP, and UASGRP in different network environments and the change of the overall residual energy of the network with the number of rounds during the operation of the protocols. In this way, the performance of different protocols can be illustrated comprehensively.

Figures 8 and 9 respectively show the changes in the number of alive nodes of the five protocols with the number of operation rounds in the 200 m × 200 m and 400 m × 400 m networks. It can be seen that the changes of alive nodes in the 200 m × 200 m network are relatively similar, because the five protocols all adopt the grid-based clustering approaches. In terms of scalability, the performance of GFTCRA and Multi-hop EEBCDA in the two network scenarios is quite different. The slopes of their curves in Fig. 9 that represent the changes of node death rate increase sharply. This indicates that they are not suitable for large-scale networks. Correspondingly, the curves of EESCA-WR, ASGRP and UASGRP are relatively stable, indicating that the communication mechanism based on bifunctional nodes adopted by these three protocols is conducive to large-scale networks. Besides, the experimental results also show that the annulus sector grid clustering approach has better performance than the rectangular grid clustering approach. Because the annulus sector grid clustering approach alleviates the hot spot problem well. The improved grid division approach of UASGRP makes the energy consumption of nodes more balanced. At the same time, because the nearest interlayer routing algorithm can reduce unnecessary energy consumption, it prolongs the network lifetime.

Fig. 8
figure 8

The number of alive nodes in the 200 m × 200 m network area

Full size image
Fig. 9
figure 9

The number of alive nodes in the 400 m × 400 m network area

Full size image

Under different network environments, the overall energy consumption changes of the networks are shown in Figs. 10 and 11. It is observed that the slope of UASGRP is significantly smaller than that of other four protocols. Smaller slope changes indicate slower energy consumption. In Fig. 10, the trends of GFTCRA, Multi-hop EEBCDA, EESCA-WR coincide basically, while the curve changes of ASGRP and UASGRP also coincide basically. This indicates that the performances of energy efficiency in the annulus sector grid clustering schemes are better than that of the rectangular grid clustering schemes. In the 400 m × 400 m network, due to the premature death of nodes close to the BS in GFTCRA and Multi-hop EEBCDA, the energy consumed by nodes far away from the BS for data transmission increases sharply. This results in a rapid reduction in the overall network energy. The overall energy decline of EESCA-WR, ASGRP and UASGRP is relatively stable. This shows the scalability of these three protocols is better and the energy consumption is relatively balanced. Compared with ASGRP, the grid division of UASGRP is more reasonable and the nearest interlayer routing algorithm reduces the communication of CM nodes close to the BS and better balances the energy consumption between different nodes. Therefore, UASGRP achieves more uniform energy dissipation.

Fig. 10
figure 10

Energy consumption of the 200 m × 200 m network area

Full size image
Fig. 11
figure 11

Energy consumption of the 400 m × 400 m network area

Full size image

To evaluate the impact of node density, we varied the number of nodes from 100 to 500 in two networks of 200 m × 200 m and 400 m × 400 m.The results are shown in Figs. 12–15. It is observed that the FND and LND of UASGRP are larger than the other four protocols, which means better performance. Besides, as the number of nodes increases in Figs. 12 and 13, the FND of these protocols raise first and then basically remain stable. This change trend is more obvious in the 400 m × 400 m network. In a certain degree, the FND is related to node density, which will limit the performance of a protocol. This phenomenon is mainly because grid-based clustering approaches cannot guarantee that the number of nodes in each cluster is approximately the same. Too few nodes in a cluster will cause some nodes to die prematurely. When the number of nodes increases to a certain extent, it can be known from the probability theory that there are enough nodes in each cluster to balance energy consumption, and protocols have better performance. As the number of nodes increases in Figs. 14 and 15, the LND basically remains unchanged. This is because the grid-based clustering scheme only performs clustering when the network is initialized. Once the distribution of grids is determined, it will not change until the network fails. In the case of random distribution of nodes, the grid-based clustering scheme determines the network lifetime to a certain extent in advance. Therefore, there is a low impact of node density on the LND of grid-based clustering schemes.

Fig. 12
figure 12

The FND of four protocols of the 200 m × 200 m network area

Full size image
Fig. 13
figure 13

The FND of four protocols of the 400 m × 400 m network area

Full size image
Fig. 14
figure 14

The LND of five protocols of the 200 m × 200 m network area

Full size image
Fig. 15
figure 15

The LND of five protocols of the 400 m × 400 m network area

Full size image

6 Conclusion

In this paper, we proposed UASGRP, an uneven annulus sector grid-based energy-efficient multi-hop routing protocol for WSNs. The proposed protocol introduces an uneven arithmetic annulus sector grid division approach to group nodes into clusters. This scheme makes the clusters closer to the BS have smaller sizes, which alleviates the hot spot problem and improves energy efficiency. UASGRP adopts the network management and communication mechanism that combines CM nodes and CHs to share the communication overhead. Besides, to reduce the number of forwarded packets and ease the load of CM nodes near the BS, UASGRP introduces a nearest interlayer routing algorithm for inter-cluster communication. Simulation results show that compared with GFTCRA, Multi-hop EEBCDA, EESCA-WR and ASGRP, UASGRP has better performances in load balancing, network lifetime and scalability. However, this work only performs clustering when the network is initialized. In the future, some heuristic algorithms will be considered to optimize clustering and further to improve the network performance in different network scenarios.