A grid-based reliable multi-hop routing protocol for energy-efficient wireless sensor networks

Abstract

Due to the limited energy and the non-equivalence of wireless sensor network nodes, it is imperative to reduce and rationally use the energy consumption of the nodes to prolong the network lifetime. Clustering routing algorithm can address the problem efficiently. In this article, a grid-based reliable multi-hop routing approach for wireless sensor networks is proposed. In order to minimize and balance the energy consumption, our proposed protocol, grid-based reliable multi-hop routing protocol, optimizes the cluster head election process by combining individual ability which consists of node’s residual energy and node’s location, and local cognition which can balance energy consumption among clusters via a consultative mechanism based on cluster head’s lifetime expectancy, while considering data forwarding delay and reliable transmission of data. Simulation results show that grid-based reliable multi-hop routing protocol has improved stability period as compared to other protocols. Meanwhile, grid-based reliable multi-hop routing protocol has better performance in energy efficiency, data forwarding delay, and reliable transmission of data.

Keywords

Wireless sensor networks routing protocol consultative mechanism network lifetime delay

Introduction

Large-scale wireless sensor networks (LS-WSNs) have attracted a lot of research interest, especially in the context of performing environmental monitoring and periodic data collection tasks. Due to the restricted energy and the non-equivalence of wireless sensor network nodes, it is imperative to reduce and rationally use the energy consumption of the nodes to prolong the network lifetime.^1,2 Routing protocol is an effective method to address the problem, in which cluster-based protocol is widely used.

In order to make the research fit the actual situation more closely, the situation of the base station far away from the monitoring area is considered in this article. The location of the base station determines the flow direction and forwarding convergence of wireless sensor network nodes. Although many routing protocols based on clustering presented in the literature minimize energy consumption on data forwarding path to enhance energy efficiency of the nodes for prolonging the network lifetime, these protocols cannot necessarily extend network lifetime when the situation of the energy cavity occurs prematurely. Furthermore, most of the protocols focus on only one optimization criteria,^3–6 such as reliability while ignoring other practical indicators, such as delay, network lifetime, throughput, and stability. Therefore, it is challenging to reach a convincing trade-offs among the various conflicting evaluation criteria, such as the network’s energy efficiency, data transmission latency, throughput, stability, reliability, and lifetime.

In this article, a grid-based reliable multi-hop routing protocol (GRMRP) is proposed. First, GRMRP divides the monitoring scenario into several virtual grids, where a virtual grid is a cluster. Then, the virtual grid is subdivided into several basic cover units, and only one node is kept in active state and other nodes go to sleep while still maintaining connectivity and coverage. An energy-triggered adaptive cluster head election (ET-CHE) strategy, combined with proactive round-robin rotation and passive adjustment, is proposed for balancing the energy dissipation in all basic cover units. Furthermore, a bilateral consultative mechanism based on cluster head’s lifetime expectancy is presented for allocating data flow reasonably among clusters. MATLAB simulation results show that GRMRP has improved stability period as compared to other protocols. Meanwhile, GRMRP has better performance in energy efficiency, data forwarding delay, and reliable transmission of data.

The main contributions of this article can be summarized as follows:

We propose a grid-based partition method for division of wireless sensor networks. GRMRP divides the monitoring area into several virtual grids (clusters) according to monitoring scene scale and node communication range, and all nodes in each grid cooperate with each other to collect data and transmit data to the sink until wireless sensor network fails to work.

Considering the significant node redundancy, GRMRP divides virtual grid into several basic cover units by comparing the size of grid and the communication range of sensor nodes, and just keeps only one node stay in active state and other nodes go to sleep while still maintaining coverage and connectivity.

We propose an ET-CHE method, using proactive round-robin rotation strategy when the energy level of cluster head is lower than the average energy level in the cluster and passive adjustment strategy when the cluster head receives feedback from the relay node, to optimize the energy dissipation among nodes in all basic cover units.

In order to balance energy dissipation among clusters and avoid the premature emergence of Energy Hole which is introduced by the unreasonable distribution of traffic load between source nodes and relay nodes, we design a bilateral consultative mechanism based on lifetime-forecast (BCM-LF). In order to determine the energy state of adjacent cluster, cluster head first selects the optimal adjacent relay node and then reselects the best forward node from other neighbors when the cluster head received negative feedback message.

The performance of the proposed protocol is evaluated with two models using MATLAB simulations. The first model uses a single indicator evaluation and the second adopts a comprehensive index model which can effectively make up the one-sided nature of the single index evaluation model. In comparison with existing data gathering protocols, our approach achieves better performance such as less latency, less energy consumption, better throughput, and high reliability which provides better quality-of-service (QoS) along with the extending of network lifetime.

The rest of the article is organized as follows. Section “Related work” gives an overview of related work. Section “Problem statement” describes our system model and states the objectives that we deal with in this work. Section “GRMRP” presents the data gathering problem, describes the details of the proposed protocol GRMRP, and argues that it meets its objectives. In section “Protocol simulation and result analysis,” we evaluate our protocol through extensive simulations by comparing it with several popular routing protocols. Finally, we give peroration and future research directions.

Related work

Our study gains inspiration from meaningful evaluation indicators such as reliability and latency and builds on related work for grid-based routing protocols^7–12 and cluster-based routing protocols.^13–28

In Farman et al.,⁴ a grid-based hybrid network deployment (GHND) framework is proposed for load balancing to ensure energy efficiency in WSNs. To evenly distribute load across the network, merge and split technique is used to achieve even distribution of sensor nodes across the grid. In GHND, low-density neighboring zones are merged together whereas high-density zones are strategically split to achieve optimum balance. Considering the nodes in LS-WSNs have the potential to be selfish without transmitting packets in routing, a reliable coalition formation routing (RCFR) protocol⁵ is proposed to address stable cooperation among nodes for packets delivery and minimum routing cost. Huynh et al.⁶ describe an investigation of the trade-off between minimizing energy consumption and minimizing end-to-end delay, propose a distributed clustering approach to determining the best cluster head for each cluster, propose two new functions for use in an inter-cluster routing algorithm by considering both energy consumption and end-to-end delay requirements, and present a multi-hop routing algorithm for use in disseminating sensing data from cluster heads to a sink at the minimum energy cost subject to an end-to-end delay constraint. In order to address the hot spot problem, a grid-based fault-tolerant clustering and routing algorithm (GFTCRA)⁷ is proposed to deal with the trade-off between energy efficiency and fault tolerance of cluster heads. In order to solve the problem of network partition, which is caused by the early dead situation of the sensors, a position-based routing algorithm⁸ is proposed to fairly use the energy of the sensors. The forwarding search space (FSS) is introduced to control unnecessary transmissions and a next forwarder selection function is designed based on the residual energy, node degree, distance, and angle. The literature⁹ has proposed a grid-based reliable routing algorithm referred as GBRR, which achieve extensibility and adaptability for random deployed sensor networks at a dense and large-scale area. In GBRR, the next hop choice is made based on intra-cluster and inter-cluster communication quality, and the problems of barrier and cavity will be addressed using greedy and perimeter forwarding strategy to make the network reliable. In Zarifzadeh et al.,¹⁹ a game-theoretic topology control framework is proposed to study the problem of creating energy-efficient topologies for ad hoc networks in the presence of selfish nodes. Since the amount of energy consumed in each sensor node depends not only on its power but also on the volume of traffic it forwards, a new utility function that can better characterize the real interest of sensor nodes in energy optimization is proposed, by taking both their load and transmission power into consideration. Energy-aware routing algorithm presented by Li and Guan²⁰ uses local betweenness centrality to estimate the energy consumption of the neighboring nodes around a given local sensor node, without global information about the network topology. In Heinzelman et al.,²² a low-energy adaptive clustering hierarchy (LEACH) routing protocol, which is a typical representative of hierarchical routing protocols in WSNs, is proposed for periodic data collection applications. In LEACH, each node independently proclaims itself as the cluster head periodically by equal probability round-robin method. Cluster heads are responsible for collecting data of member nodes and delivering the aggregated data to the remote sink by single-hop communication. The advantages of LEACH protocol are it is easy to be implemented and it has no need for central control, but the performance such as scalability in heterogeneous networks and LS-WSNs is not well mainly because the far distance nodes will first run out of energy, not consider the energy level of nodes, the uneven distribution of cluster heads, and the difference in the number of cluster heads is very obvious. Hybrid energy-efficient distributed (HEED) clustering²³ is a typical distributed clustering approach, periodically selects cluster heads according to a hybrid of the node residual energy and a secondary parameter, such as node proximity to its neighbors or node degree. The merit of HEED is that it can asymptotically almost surely guarantee connectivity of clustered networks. In Xu et al.,²⁴ a geography-informed energy conservation for ad hoc routing (GAF) is proposed to reduce energy consumption. GAF is a typical topology management protocol in which sensor nodes are classified into equivalence classes based on their position information and some nodes in each class participate in data acquisition and transmission, while other nodes are turned off for saving energy. In GAF, the location information of node can be obtained from a orientation system such as GPS. Power-efficient gathering in sensor information systems (PEGASIS)²⁵ is a position-based geographic routing protocol, which forms a chain in which all nodes can only transmit and receive message from the nearest neighbor nodes. In PEGASIS, only one node will directly deliver the aggregated data to the sink each round. Although PEGASIS is attractive due to its efficiency and scalability, it is confirmed that there would be still considerable room to optimize the performance such as low fault tolerance and too large latency. In order to mitigate the hot spot problem in multi-hop sensor networks, an unequal cluster-based routing (UCR)²⁸ protocol which groups the nodes into clusters of unequal sizes is proposed. In UCR, cluster heads closer to the sink have smaller cluster sizes than those farther from the sink, thus can preserve some energy for the inter-cluster data forwarding. In order to mitigate the overhead caused by frequent cluster head selection, a modified weight based cluster head selection algorithm with balanced partitioning (BP-DCA)¹⁵ is presented for WSNs. BP-DCA considers the node’s residual energy, number of neighbor nodes, average distance between the nodes for selecting the best nodes as cluster heads, and distance between the cluster heads for optimum distribution of cluster heads during cluster formation. Table 1 summarizes related work for grid-based routing protocols and cluster-based routing protocols.

Table 1.

Comparative analysis of the selected routing protocols.

Protocol	Problem specification	Technique
LEACH	Cluster-based routing protocol	Hierarchical routing protocol, distributed and localized cluster head selection based on equal probability round-robin method
HEED	Cluster-based routing protocol	Heuristic solution to select cluster head
GAF	Position-based geographic routing protocol	Equivalent class method and dormancy mechanism
PEGASIS	Position-based geographic routing protocol	An adaptive algorithm based on the idea of greed
DEEC	Cluster-based routing protocol	The cluster heads are elected based on the ratio between residual energy of each node and the average energy of the network
UCR	An unequal cluster-based routing protocol	Set different size of the cluster based on position of cluster head
GBRR	Grid-based topology algorithms	A greedy algorithm is used to solve the barrier and cavity problems
RCFR	Reliable delivery mechanism in WSNs	A coalitional game model
Huynh et al.⁶	Cluster-based multi-hop routing protocol	An investigation of the trade-off between energy consumption and delay
GFTCRA⁷	Grid-based topology algorithm	Deal with the trade-off between energy efficiency and fault tolerance
Kumar and Kumar⁸	Position-based routing algorithm	FSS method and Heuristic solution is used to select the next relay cluster head
GHND	Grid-based topology algorithm	Uses merge and split technique for load balancing
Li and Guan²⁰	Energy-aware routing algorithm	Local betweenness centrality
Zarifzadeh et al.¹⁹	Cluster-based routing protocol	Game-theoretic topology control framework
BP-DCA	Cluster-based routing protocol	Heuristic solution to select cluster head based on weight

LEACH: low-energy adaptive clustering hierarchy; HEED: hybrid energy-efficient distributed; GAF: geography-informed energy conservation for ad hoc routing; PEGASIS: power-efficient gathering in sensor information systems; DEEC: distributed energy efficient clustering; UCR: unequal cluster-based routing; GBRR: grid-based reliable routing; RCFR: reliable coalition formation routing; GFTCRA: grid-based fault-tolerant clustering and routing algorithm; GHND: grid-based hybrid network deployment; BP-DCA: modified weight based cluster head selection algorithm with balanced partitioning; WSN: wireless sensor network; FSS: forwarding search space.

Problem statement

Cluster-based routing protocol for WSNs is closely related to specific application scenarios, in which monitoring tasks have the same essence, being a number of sensor nodes deployed randomly within a given region by throwing manner. Nodes send collected data to the sink by single-hop or multi-hop wireless transmission. In the following section, we first describe the network model, transmission model, data fusion model, and running time model and then give our objectives.

Network model

In this article, we consider a sensor network consisting of N sensor nodes uniformly dispersed within a vast monitor field to continuously monitor the environment. We denote the ith node by $s_{i}$ and the corresponding sensor node set $S = {s_{1}, s_{2}, \dots, s_{N}}$ . To simplify the network model, we adopt a few reasonable assumptions as follows:

All sensors are left unattended after deployment and have unique identification; the sensor nodes can be accurately located by GPS or some localization algorithm. All sensor nodes are quasi-stationary after deployment.

The energy of sink is unlimited, with strong computing and storage ability. Considering the need of real application, the sink is located far away from the sensing field.

All nodes have limited initial energy and nodes with different energy have different data-collecting abilities. The energy depletion of sleep nodes can be neglected.

Data within different fields have different requirements concerning the transmission delay to the sink.

Links are symmetric, that is, two nodes can communicate with each other using the same transmission power level. All sensor nodes can communicate directly with sink when their energy are allowable.

Each node has a fixed number of controlling transmission power level and can use power control to vary the level of transmission power according to the distance to the desired recipient.

The data sensed by adjacent sensor nodes are highly correlative, and all nodes have data fusion ability to eliminate the data redundancy and reduce the communication load.

Energy model

GRMRP protocol uses the same radio hardware energy dissipation model as that of Heinzelman et al.²² Readers may refer to Heinzelman et al.²² for more details. To transmit a k-bit message for a distance of d, the energy consumption is

\begin{matrix} E_{Tx} (k, d) = E_{elec} (k) + E_{amp} (k, d) \\ = {\begin{matrix} k \times E_{elec} + k \times ε_{fs} \times d^{2}, d < d_{0} \\ k \times E_{elec} + k \times ε_{mp} \times d^{4}, d > d_{0} \end{matrix} \end{matrix}

(1)

E_{Rx} = E_{elec} (k)

(2)

The energy consumption model used in this article only considers the energy consumption in node sending and receiving the message, ignoring that produced in the process of computing and storage. The node energy consumption is proportional to the square of the distance d if $d < d_{0}$ , otherwise proportional to the quartic of the distance d.

Data fusion model

Data fusion or aggregation has emerged as a useful paradigm in sensor networks. The key idea is to combine data from different sensors to eliminate redundant transmissions and provide a rich, multi-dimensional view of the environment being monitored. Gathered data moves from node to node, gets aggregated, and is eventually transmitted to the sink. To maximize the lifetime of the system, GRMRP uses data fusion technology to achieve the goal of saving and balancing energy consumption performance. We assume that all nodes have the same perception radius and the capability of aggregating its data packets. Cluster head collects n number of k-bit data from member nodes in the cluster and compresses it to cn k-bit messages with c ≤ 1. As there is a big difference in the data correlation of different clusters, we just consider transmission instead of data fusion among cluster heads; and the energy consumption of data fusion $E_{DA}$ is 5 nJ/bit.

System runtime model

Because of the difference in the initial energy of nodes, we assume that the number of data packet collected by each sensor node per time unit is proportional to the initial energy of each node. For simplicity, we refer to each time unit as a round based on LEACH protocol.²² Similar to LEACH, the operation of cluster head election scheme is composed of cluster formation phase and data transmission phase. Network running time series model is shown in Figure 1.

Figure 1.

Network running time series model.

Figure 1 illustrates the running time of GRMRP. In the initial operation stage T_init, the monitoring area is divided into a number of small virtual grids based on the node communication range $R_{t}$ , and each grid is a cluster. $T_{round}$ denotes runtime for nodes self-organizing themselves into local clusters. Since the clustering formation of GRMRP occurs only once, the overhead of GRMRP is very small. In order to reduce the system energy consumption which is caused by frequently cluster head election, energy-triggered adaptive cluster head adjustment strategy is adopted in GRMRP, and the trigger condition depends on the relationship between the energy of cluster head and average energy of the cluster. We will explain it in more detail in section “Energy-driven cluster head round-robin method.”T_{cluster-select} denotes the time of cluster head election, T_to-cluster indicates the time of intra-cluster data collection, and T_{cluster-router} indicates the time of inter-cluster data transmission.

GRMRP presented in this article aims to reduce nodes energy dissipation, balance network energy expenditure, shorten data forwarding delay, and increase network lifetime with the premise to ensure complete network coverage and monitoring quality. Security is not considered here.

GRMRP

To address the problem of quickly network energy consumption, unbalanced node energy dissipation, and overlong delay in data aggregation, we propose an efficient GRMRP, which can reasonably make use of the node energy and effectively prolong the network lifetime through using virtual grids to organize network topology, eliminating hot spot problem by adopting negotiation strategy which can predict lifetime, and dynamic cluster head adjusting strategy.

Network initialization phase

Consider the total number of sensor nodes N is randomly scattered in a given targeted scenario, the area of which is $L \times W$ , where L and W are the length and width of the scenario, respectively, as shown in Figure 2. In this article, we assume all nodes are aware of their energy, geographical location, and unique node ID. Once the deployment of network topology is completed, all sensors report their configuration information to the sink. Then, the base station begins to broadcast the message of grid division when it receives all sensors information.

Figure 2.

Grid formation.

Cluster formation

We propose an adaptive grid formation algorithm (AGFA) to divide the monitor field into virtual grids and construct network topology whose details are presented in Algorithm 1. The base station divides the whole monitoring field into $Row \times Col$ virtual grids based on the size of monitoring field and cluster head transmission range R_t. The definition of virtual grid is similar to that of Xu et al.,²⁴ and the relationship between each grid and its neighboring eight grids is that all the nodes in this grid can communicate with all the nodes in the neighboring eight grids, while in Xu et al.²⁴ each grid can communicate with its neighboring four grids. Figure 2 shows grid formation where sensor nodes are uniformly distributed in N_x × N_y grids and each grid is referred as a cluster, identified by a unique grid number $g_{row, col}$ . As shown in Figure 2, R_t denotes the transmission range of sensors and r denotes the radius of grid’s circumcircle, which is the minimum radius under the ideal condition. In order to meet the coverage requirement of practical application, 2r is the maximum radiation radius of the cluster head to cover the monitoring area to which it belongs to ensure network monitoring quality. Figure 2 illustrates R_t can meet the connectivity of adjacent grids, ensuring the communication between two possible farthest nodes in any two adjacent grids. From Figure 2, we can get $R_{t} = 2 R_{c}$ and $R_{c}^{2} = l^{2} + w^{2}$ .

Algorithm 1. Algorithm AGFA for dividing the monitor field into virtual grids
Input: L, W, Rt, N
Output: $Loc (g_{row, col})$
Initialization: $l = w = 0$ ; $Loc = \emptyset$ ;
Step 1: Calculate the size of l and w;
1.1 $l = w = sqrt (R_{t}^{2} / 8)$ ;
1.2 $Nx (l) = Nx (w) = ⌈ L / l ⌉$
1.3 $l = w = L / Nx (l)$ ;
Step 2: Determine the virtual center of virtual grid
2.1 for Row = 1:Nx
2.2 for Col = 1:Ny
2.3 $G_{x} = (Row - 1) \times l / 2$ ; $G_{y} = (Col - 1) \times l / 2$ ;
2.4 $Loc (g_{row, col}) = (G_{x}, G_{y})$
2.5 end for
2.6 end for
return $Loc (g_{row, col})$
end for

In this article, just square grid is considered.

By comparison, we can see that our proposed grid formation algorithm has better adaptability than GHND which needs to know the number of grids in advance.

Basic cover unit formation

To meet the requirement of application in real life, high-density node deployment strategy is used in network deployment, and all the virtual grids in the network are covered with high probability. Assume that the size of the monitoring area is known, and it is divided into W virtual grids, with N nodes distributed uniformly and dispersed randomly within the W virtual grids, then the probability of any grid being not covered is $(1 - (1 / W))^{N}$ . For instance, the size of the monitor scenario is $200 \times 200 m^{2}$ and the size of each grid is $50 \times 50 m^{2}$ , the number of sensor nodes N is 200, then we can get the number of grids M is 16 and the probability of any designated grid not being covered is $(1 - (1 / W))^{N} = (1 - (1 / 16))^{200} \approx 0.000002478$ , thus we can see that the probability of sensor nodes falling in each grid will be as high as 99.99% in WSNs nodes deployed in high density. With each gird having nodes, we can guarantee the network connectivity proposed in the virtual grid formation phase.

Due to the randomness of the node distribution, some nodes are densely distributed in the same grid and resulting in high redundancy of data which is bound to increase network traffic and cause unnecessary system energy consumption, as shown in Figure 2. In order to save network energy and ensure the quality of network monitor, this article proposes a perception-based intra-cluster subdivision algorithm (PISA) that effectively eliminates the node redundancy to reduce the network data traffic and guarantee the data forwarding delay as much as possible. The details of PISA are presented in Algorithm 2.

Algorithm 2. Algorithm PISA for dividing the virtual grid into basic cover units
Input: l, Rs, Rc
Output: $Set_Unit$ ;
Initialization: $Set_Unit = \emptyset$ ;
Step 1: Compare the size of Rs and Rc;
1.1 $if (Rs > Rc) then go to Step 3$ ;
1.2 $if (Rs < Rc) then go to Step 2$ ;
Step 2: Determine the size of basic cover unit
2.1 $num_side_unit = ⌈ Rc / Rs ⌉$ ;
2.2 $size_unit = l / num_side_unit$ ;
2.3 determin the total number of units using Algorithm 1 (Step 2);
Step 3: $size_unit = l$ ;
Step 4: return $Set_Unit$
4.1 $if (size_unit = l)$ return ‘the grid does not need to be divided’;
4.2 else return $Set_Unit$ ;

In algorithm PISA, we need to consider the relation between the sensor nodes’ perception radius R_s and the cluster size l. As shown in Figure 2, not all nodes in the cluster can cover the entire grid when $R_{c} > R_{s}$ , then the cluster needs to be subdivided into $m \times m$ basic cover units. To ensure each basic cover unit is covered by nodes, we can get $(l / m)^{2} + (l / m)^{2} \leq R_{s}^{2}$ . Once the clusters are divided, nodes in each cluster will find the basic cover unit which they belong to, as is shown in Figure 3. Since the node density within each basic cover unit is very different, we introduce the dormancy mechanism proposed in Xu et al.²⁴ to save energy, allowing only one node in each basic cover unit to be active while others are in the state of sleep. The number of active nodes in all clusters is the same $m^{2}$ , so the energy consumption in each cluster is similar and the delay of data collection and integration in each cluster is approximately the same. Based on the above analysis, the probability of nodes’ falling into each sub-grid is still as high as 95.7% when $m = 2$ . Even if there are no nodes in a given basic cover unit A, the adjacent basic cover units have a high percentage of cover over its monitoring area. As shown in Figure 3, when the neighbor cluster head is located at the center of its adjacent unit B, the covered area in unit A is $\int_{- l / 2 m}^{l / 2 m} \sqrt{2 {(l / m)}^{2} - x^{2}} d x - \frac{{(l / m)}^{2}}{2} \approx 88.42 %$ . Besides, whole network coverage can be achieved by increasing the node density.

Figure 3.

Minimum coverage example.

Active node election method

To make a reasonable use of the node energy, this article adopts the self-recommendation model to elect active nodes whose details are presented in Algorithm 3. The competitive power of the nodes will be the key factor. It is computed as follows

C (g_{i, j}, h) = \propto (1 - \frac{E_{\max} - E_{res}}{E_{\max}}) + (1 - \propto) (1 - \frac{d_{v}}{R_{m}})

(3)

$g_{i, j}$ indicates cluster (i, j), and h is the serial number of basic cover units in cluster $g_{i, j}$ ; v is the virtual center in the basic cover unit; R_m is the diagonal distance of the basic cover unit; $d_{v}$ is the distance between the node and the virtual center; E_max is the largest initial energy of nodes in the monitoring area; E_res is the residual energy; $\propto$ is the weighting coefficient of self-adaptation, and $\propto = (E_{init}) / (E_{init} + E_{res})$ , then the nodes with advantageous geographical location and high residual energy will have priority to be elected as active nodes.

Algorithm 3. Self-recommendation model to elect active nodes
Input: E_max, h, $d_{v}$ , $g_{i, j}$ , and $T_{\max}$ ;
Output: node_ID;
Initialization: $C (g_{i, j}, h) = 0$ , node.receive_flag == “FALSE”; node.active = “FALSE”;
Step 1: calculate the coefficient of $α$ according to its energy;
Step 2: calculate the $C (g_{i, j}, h)$ according to equation (3).
Step 3: set the timer of the node and then the timer starts;
Step 4: timer–;
4.1 if (timer == 0) broadcast message ACTIVE_MSG;
4.2 node.active = “TRUE” and turn to Step 7;
Step 5: execute operations based on the received message
5.1 if (node.receive_flag == “FALSE”) go to Step 4;
5.2 if (node. receive_flag == “ACTIVE_MSG”) go to Step 6;
Step 6: timer stops
6.1 sends the energy of the node to the active node;
6.2 turn off the radio and sleep;
Step 7: receive the energy information of all the other nodes in the same unit
7.1 calculate the value of $E_{avg}^{sleep}$
7.2 calculate the value of $E_{total}^{sleep}$
Step 8: the active node test its energy node.energy
8.1 if (node.energy < $E_{avg}^{sleep}$ ) broadcast the message RE-ELECT_MSG
8.2 else continue
Step 9: all the other nodes receive the message RE-ELECT_MSG
Algorithm 3 restarts the election of a new active node

The node’s competitive power $C (g_{i, j}, h)$ reflects the capacity of the node to join in the competition for active node. Not only the node energy but also the load conditions within the cluster is considered. The cluster load of $C (g_{i, j}, h)$ is intrinsically different from the cluster communication cost in HEED because v in HEED is the geometric center of the basic cover unit while v in equation (3) is the nearest point from the basic cover unit to the sink, whose range of value consists of the four vertexes of the basic cover unit and the midpoint of the four edges. Comparatively speaking, the selection of v is closely related to the location of sink node and has certain self-adaptation. When basic cover units are fixed, the competitive power of each node can be calculated by the equation (3) and then the timer starts whose length T is defined as

T = T_{\max} (1 - C (g_{i, j}, h))

(4)

In the above equation (4), T_max is the initialized fixed time. The node broadcasts message ACTIVE_MSG to an area of the radius of R_m when the timer stops, announcing it has become the active node of the basic cover unit. The competitive power of the node is also broadcast in the message. If a node receives the message ACTIVE_MSG broadcast by other nodes before the timer stops, then the timer stops working and enter the state of sleep after sending its own energy to the active node. The message ACTIVE_MSG contains the node ID, location, and energy. Once the active node receives all the energy from the other nodes, it begins to calculate average energy $E_{avg}^{sleep}$ and total energy $E_{total}^{sleep}$ of other nodes and saves the results.

EANAS: energy-driven active node adjustment strategy

Since frequent interaction between active nodes will consume certain system energy, an energy-driven active node adjustment strategy (EANAS) is adopted to balance the energy depletion within the basic cover unit. The details of EANAS are presented in Algorithm 4.

Algorithm 4. Algorithm EANAS for active node rotation
Input: $E_{avg}^{sleep}$ , $E_{res}^{alive}$
Output: Adjust_flag;
Initialization: Adjust_flag = “FALSE”;
Step 1: the active node test its energy node.energy
1.1 if ( $E_{res}^{alive}$ < $E_{avg}^{sleep}$ )
1.2 The active node broadcasts the message WAKEUP_MSG and turns to Step 2
Step 2: when all the other nodes receive the message WAKEUP_MSG
2.1 Adjust_flag = “TRUE”
Step 3: test the status of Adjust_flag
3.1 if (Adjust_flag == “FALSE”)
the active node continue the next round of data acquisition
3.2 if (Adjust_flag == “TRUE”)
call Algorithm 3 and restarts the election of a new active node

When the energy of active node is lower than $E_{avg}^{sleep}$ , the active node will broadcast WAKEUP_MSG message to wake up all the sleep nodes to join in the election of being active node. If the active node is not cluster head, then it enters the state of sleep by closing the radio after informs the new cluster head the contents of ACTIVE_MSG, and waits to be waken up to join in the next round of active node reelection. If the active node happens to be the cluster head, it informs the new cluster head information about $E_{avg}^{sleep}$ , $E_{total}^{sleep}$ , and next-hop relay node and enters the state of sleep only after the new active node is elected. When the new cluster head is elected, it broadcasts CH_MSG message in the cluster to keep the connectivity with other active nodes.

Dynamic cluster head election phase

The communication energy consumption of nodes mainly includes those produced in sending or receiving controlling message (CM) and data message (DM) during network initialization and operation stage. Although the values of CM and DM are fixed and DM >> CM, a large number of literature studies have shown that broadcasts of CM in frequent cluster heads election have resulted in significant system energy consumption.

Dormancy-dominate cluster head election method

To select proper node to work as the cluster head, an ET-CHE method, combined with proactive round-robin rotation and passive adjustment, is proposed for balancing the energy dissipation in all basic cover units. The details of ET-CHE are presented in Algorithm 5.

Algorithm 5. Algorithm ET-CHE for electing cluster head
Input: $g_{i, j}$ , $E_{sum} (g_{i, j})$ , $R_{c}$ , $d_{ch}^{pre}$ , and $\bar{E_{sub}}$ ;
Output: node_ID, num_unit;
Initialization: node_ID = 0, num_unit = 0, node.ch = “FALSE”;
Step 1: calculate the coefficient of $β$ according to its energy
Step 2: test the qualification of the active node
2.1 if $E_{sub} (h) > \bar{E_{sub}}$ then go to execute Step 3;
2.2 if $E_{sub} (h) < \bar{E_{sub}}$ then go to execute Step 5;
Step 3: calculate the value $C_{prob} (g_{i, j})$ according to equation (5).
4.1 set the timer of the active node according to equation (4) and replace $C (g_{i, j}, h)$ with $C_{prob} (g_{i, j})$ ;
4.2 if (timer == 0) broadcast CH_MSG, save node_ID, num_unit and set node.ch = “TRUE”;
4.3 else timer–;
Step 4: execute operations based on the received message
5.1 if receive the message CH_MSG, timer stops and set node.ch = “FALSE”;
5.2 else go to and execute 4.2 in Step 3;
Step 5: set node.ch = “FALSE” and wait pending until the arrival of the message CH_MSG;
Step 6: whe all the active node with node.ch=‘FALSE’ received the message CH_MSG
These nodes send message JOIN_MSG to the cluster head
return node_ID, num_unit;

In ET-CHE, we endow the active nodes different probability of being elected as cluster head based on the energy of sleep nodes in the basic cover unit. The node probability for becoming a cluster head is computed as follows

\begin{matrix} C_{prob} (g_{i, j}) = β \times \frac{E_{sub} (h)}{E_{sum} (g_{i, j})} + (1 - β) \\ \times \frac{R_{c} - d_{ch}^{pre}}{R_{c}}, if E_{sub} (h) \geq \bar{E_{sub}} \end{matrix}

(5)

where $E_{sub} (h)$ is the total energy of the sleep nodes in basic cover unit h in cluster $g_{i, j}$ ; $E_{sum} (g_{i, j})$ is the total energy of all the sleep nodes in cluster $g_{i, j}$ ; R_c is the longest distance between the nodes in the cluster and the cluster head in last round; and $d_{ch}^{pre}$ is the distance between the active node and the cluster head in last round. $C_{prob} (g_{i, j})$ shows the premise for active node to be selected as cluster head, that is, the energy of the basic cover unit which the active node belongs to is larger than the average energy of the cluster. Besides, $β$ is the self-adaptation weighting coefficient, and $β = (E_{sub}^{init}) / (E_{sub}^{init} + E_{sub}^{sleep})$ . From equation (5), $C_{prob} (g_{i, j})$ considers more about the overall competitive power of the basic cover unit rather than the individual competitive power of the current active node. Combined with the self-adaptation of $β$ , ET-CHE cluster election algorithm can use the basic cover unit with dense nodes and intensive energy first and protect the basic cover unit with sparse nodes and deficient energy, then the energy consumption of nodes in different regions in the cluster is well-balanced.

Cluster announce information

Once the cluster head has been selected, it needs to broadcast CH_MSG information in the cluster within the range of radius R_c, and other active nodes in the cluster choose it as the cluster head on receiving the information CH_MSG and send the information JOIN_MSG to join in. According to the size of the cluster, we know the whole network coverage can be achieved only when $R_{c} \geq \sqrt{2} l$ .

Energy-driven cluster head round-robin method

Ensuring optimal node acts as cluster head each round requires frequent interaction of active nodes, which will bring certain system energy consumption. In this article, an energy-driven cluster head round-robin strategy is adopted to solve the problem. Through equation (5) we know the cluster head in current round will broadcast CH_ADJUST_MSG message to perform the algorithm ET-CHE when the unit it belongs to contributes so much energy that it leads to the fact that the energy in its unit is lower than the average energy in the cluster. According to equation (5), there is no need to change the cluster head when the basic cover unit which the cluster head belongs to is full of energy. But what we need to pay attention to is that the cluster head in current round will spontaneously switch from active state to dormant state within the basic cover unit it belongs to when its energy is lower than $E_{avg}^{sleep}$ and thus change the cluster head, and details are explained in section “EANAS: energy-driven active node adjustment strategy.”

Besides, the adjustment of cluster head can also be affected by the change in next-hop data relay node. For more detailed account, please see step 5 of algorithm BCM-LF in section “Reliable multi-hop routing.”

Reliable multi-hop routing

In single sink static WSNs, fixed sink leads to asymmetrical characteristics of network nodes. The location of the sink determines the communication data flow in the network and the route of data aggregation, which means data flows toward the sink and becomes intensified near it. Therefore, the key in designing routing protocol is to solve the problem of allocating the data forwarding probability of sensor nodes in a reasonable and balanced way.

To mitigate the hot spot problem, a BCM-LF is introduced to balance the forwarding probability of relay nodes. In BCM-LF, mixed communication model of direct cluster head transmission and multi-hop transmission is adopted. The idea behind algorithm BCM-LF is to judge whether the cluster head is qualified for data routing through negotiation between cluster heads. The negotiation message consists of source cluster head ID, estimated hop number, relay node ID, and $T (g_{i, j}, r)$ . Source cluster head ID shows the data sender; estimated hop number indicates the estimated delay in data submission; relay node ID gives the possible data forwarding node; $Loc (g_{row, col})$ of relay node in BCM-LF is the predictive value of the cluster $g_{i, j}$ in which the forwarding node is located at the beginning of rth round data collection, which depend on the cluster energy and the distance between cluster head and sink in the last round. The lifetime $T (g_{i, j}, r)$ of relay node is computed as follows

T (g_{i, j}, r) = \frac{E_{sum}^{r} (g_{i, j}) - E_{g_{i, j}}^{th}}{d (g_{i, j}^{v}, {Ch}_{next}^{r - 1})}

(6)

where $E_{sum}^{r} (g_{i, j})$ denotes the total energy of all sleep nodes in cluster $g_{i, j}$ in round r; $E_{g_{i, j}}^{th}$ denotes the energy threshold sum of nodes with early warning failure in cluster $g_{i, j}$ ; $d (g_{i, j}^{v}, {Ch}_{next}^{r - 1})$ denotes the distance between the virtual center of cluster $g_{i, j}$ and that of the cluster which contains the cluster head in last round forwarding.

The executive steps of algorithm BCM-LF are as follows:

Step 1. Cluster head sets initialized lifetime and forms ideal routing forwarding path. That is, each cluster head gets and forms the list of its neighboring cluster heads according to the node’s communication radius, selects the cluster which is nearest to itself as its tacit routing forwarding cluster along the $\max {X_{sink}, Y_{sink}}$ axis direction.

Step 2. All cluster heads working for data transmission are evaluated on transmission qualification once the ideal routing forwarding path is formed. The cluster head is first evaluated on whether it has absolute data transmission capacity, that is, whether the residual energy of cluster head is larger than that needed for sending its own data and data to be forwarded to the next-hop nodes, including sink. The evaluation method is as follows

E_{intra} + E_{relay} + E_{self} < E_{res} - E_{i}^{th}

(7)

where $E_{intra}$ denotes the energy consumption by cluster head in collecting data and data fusion of member nodes, $E_{relay}$ denotes the energy consumption in cluster head’s receiving and transmitting data to be forwarded, and $E_{self}$ denotes the energy consumption in the forwarding of cluster head’s own data. $E_{res}$ is the residual energy of the cluster head; $E_{i}^{th}$ is energy warning threshold of cluster i. If the condition is met, then continue the follow-up operation, otherwise, turn to execute step 7.

Step 3. The position relation of the adjacent cluster heads which communicate with each other on the ideal route forwarding path is compared. If the relay cluster is farther away from the sink than the source cluster head, just ignore this section. Otherwise, if the relay cluster head is closer to the sink, next is to evaluate whether data transmission will save network energy consumption. It is computed like this

\frac{E_{s} (s, d) + E_{relay} (d, sink)}{E_{res} (s) + E_{res} (d)} < \frac{E_{s} (s, sink)}{E_{res} (s)}

(8)

where s denotes the cluster head which sends data transmission request; d denotes the neighboring cluster head which decides whether to reply data transmission; $E_{s} (s, d)$ denotes the energy consumed in the data transmission from cluster head s to cluster head d; $E_{relay} (d, sink)$ denotes the energy needed by cluster head d to transmit data to the sink; $E_{res} (s)$ denotes the residual energy of cluster head s; $E_{res} (d)$ denotes the residual energy of cluster head d; $E_{s} (s, sink)$ denotes the energy needed by cluster head s to directly transmit data to the sink; if equation (8) is met, then we can conclude that the collaboration of cluster s and cluster d will save network energy consumption, and it is meaningful for data forwarding.

Step 4. We need to judge whether the lifetime difference between two cluster heads is reasonable. Here is how to make the judgment*

T (g_{d}) > δ \times T (g_{s})

(9)

where the value of $δ$ is larger than 0. If the condition for equation (9) is met, then Step 5 will be executed, otherwise, step 7 is executed. From equation (9), cluster head energy consumption can be effectively balanced and early occurrence of network energy hole can be avoided using algorithm BCM-LF.

Step 5. Cluster head d sends message RELAY_OK_MSG to cluster head s. Message RELAY_OK_MSG includes the location, cluster head ID, and the number of its basic cover unit. When cluster head s receives message RELAY_OK_MSG, it will compare whether its own unit number is equal to the unit number in cluster d. If the two numbers are equal to each other, it is ready to send data. If the two numbers are not equal, then an active node set will be found satisfying the condition $E_{sub} (h) > \bar{E_{sub}}$ . If the active node set is not empty, to determine whether there exists an active node has the same unit number as cluster d. If this active node is found, execute step 6. If this active node is not found, determine whether there exist active nodes whose distance from cluster d is shorter than itself. If found, we select the active node whose distance from cluster d is the shortest and execute step 6.

Step 6. Message CH_ACT_MSG from cluster s is sent to notify it to be the cluster head, and the new cluster head in cluster s broadcasts information CH_NEW_MSG to inform the adjacent cluster head the change of cluster head. Message CH_ACT_MSG contains relevant information of the request node and relay node.

Step 7. Cluster head d sends message REFUSE_MSG to cluster head s, which shows that cluster d at present is lack of energy and incapable of providing data transmission service for cluster s. After cluster s receives this message, it sends data transmission request message REQUEST_MSG to its neighboring cluster heads for data forwarding.

Step 8. When the neighboring cluster head p receives message REQUEST_MSG, it first judge the relationship between $d (o, sink)$ and $d (s, sink)$ . If $d (o, sink) < d (s, sink)$ and neighboring cluster head meets equations (7)–(9), then Step 9 will be executed; otherwise, it replies message REFUSE_RELAY_MSG. If $d (o, sink) \geq d (s, sink)$ and neighboring cluster head meets equations (7) and (9), then Step 9 will be executed; otherwise, it replies message REFUSE_RELAY_MSG.

Step 9. The neighboring cluster head replies message CANDI_RELAY_MSG to the request cluster head s, indicating that it can provide data transmission service for cluster head s.

Step 10. If cluster head s has not received message CANDI_RELAY_MSG in a given time interval, it will transmit data directly to the sink using direct transmission model. If cluster head s receives one or more message CANDI_RELAY_MSG, a relay node selection method based on priority is adopted in algorithm BCM-LF to choose the best nodes for data forwarding. Only when the candidate assembly with top priority is empty does cluster head s select node in the low-priority candidate assembly. In the candidate node set assembly with same priority, cluster head s will pick up the node with highest $E_{sum}^{r} (g_{i, j})$ to transmit data.

GRMRP data communication

Data forwarding routing becomes stable in data communication after the phases of cluster formation, active node election, and cluster head confirmation.

For simplification, this article adopts the same intra-cluster data-collection method as that in Heinzelman et al.²² Once the cluster is formed, each cluster head i will create a TDMA schedule for all the active member nodes j in the cluster and then broadcast to allocate a data communication slot for each active member node. Each active member node sets a timer according to TDMA schedule and wake up to send data in the fixed time, after which enters the state of sleep to save energy.

In the intra-cluster data collection, each member node only needs to deliver the sensing data to its cluster head, the energy consumption of active member node j is

E_{m} (j) = E_{elec} \times k + k \times ε_{coff} \times d^{θ} (j, C H_{j} (i))

(10)

where $C H_{j} (i)$ is the cluster head i that member j belongs to and $d (j, C H_{j} (i))$ is the distance between the member j and its cluster head $C H_{j} (i)$ , the value of $θ$ and $ε_{coff}$ is related to $d (j, C H_{j} (i))$ from equation (1).

The energy consumption of cluster head i consists of $E_{rec} (i)$ , $E_{fuse} (i)$ , and $E_{fwd} (i)$ . It is computed as follows

E_{CH} (i) = E_{rec} (i) + E_{fuse} (i) + E_{fwd} (i)

(11)

E_{rec} (i) = E_{elec} \times (k_{m} \times Nu m_{mem} (i) + k_{s} \times Nu m_{relay} (i))

(12)

E_{fuse} (i) = E_{DA} \times k_{m} \times Nu m_{mem} (i)

(13)

E_{fwd} (i) = k_{s} \times Nu m_{relay} (i) \times (E_{elec} + ε_{coff} \times d^{θ} (i, Des (i)))

(14)

where $E_{rec} (i)$ denotes the energy dissipation of cluster head i spent for receiving all intra-cluster data, $E_{fuse} (i)$ indicates the energy dissipation of cluster head i spent for fusing all intra-cluster data into a single packet to reduce redundancy, $E_{fwd} (i)$ indicates the energy dissipation of cluster head i spent to transmit $k_{m} \times Nu m_{mem} (i)$ bit data to its next hop node $Des (i)$ and $d^{θ} (i, Des (i))$ is the distance between the cluster head i and its next hop $Des (i)$ .

The cluster head aggregates the data after collecting all the data from member nodes and then sends the data to the sink according to the formed routing.

Protocol simulation and result analysis

To evaluate and compare the protocol GRMRP with other protocols such as DIRECT, LEACH, HEED, DEEC, and UCR, we evaluate the performance of the GRMRP protocol via simulations using MATLAB (version 2014b). For the experiments, we consider a $100 \times 100$ square meter area and a $75 \times 150$ rectangle meter area in which 300 sensor nodes are randomly deployed. In the simulation, specific simulation parameters are given in Table 2, in which the parameters of radio model are the same as those in LEACH.

Table 2.

Simulation parameters.

Parameter	Value
Initial energy	0.5 J
N	300
R_t	75 m
R_s	18 m
DM_size	4000 bit
CM_size	100 bit
e_fs	10 nJ/bit/m²
Sink(x,y)	(W/2, L + 50)
e_mp	0.0013 nJ/bit/m²
E_DA	5 nJ/bit
c	0.5
L, W	100, 100

First we study the effect of parameter $δ$ on the performance of the protocol, and then we investigate the size of basic cover unit of GRMRP. Because this article focuses on energy routing in the network layer, an ideal MAC layer and error-free communication links are assumed for simplicity.²⁸ For these simulations, energy consumption mainly includes that in data receiving, data transmitting, and data merging. Because LEACH, HEED, DEEC, and UCR are typical self-organized cluster-based protocols, we use the four protocols for comparison. In order to make the research fit the actual situation more closely, the sink is far from the monitoring area, and two cases of nodal initial energy homogeneity and heterogeneity are considered, and the number of nodes range from 100 to 600. This model helps compare the effects of these protocols to mitigate the severe hot spot problem and evaluate the scalability of the GRMRP protocol.

Parameter setting

There is an important parameter in GRMRP, namely $δ$ . In this part, we study the effect of parameter $δ$ on the performance of the protocol in terms of network lifetime and data forwarding delay. We measure the network lifetime in terms of the data collecting rounds when the first node fails to work for simplicity.

First, we test the effect of $δ$ on the network lifetime under two different monitoring scenes, in which one is $100 \times 100$ square meter area and the other is $75 \times 150$ rectangle meter area. Figure 4 gives the relation between parameter $δ$ and the network lifetime. There exists a different optimal value of $δ$ , where 0.5 is the optimal value in $100 \times 100$ square meter area and 0.4 is the optimal value in $75 \times 150$ square meter area. Due to the influence of the position of the base station, the value of $δ$ increases with the increase in distance between the sink and the monitoring scene. According to the setting of the scene in Table 2, we choose the value of the parameter to be $δ$ 0.5.

Figure 4.

The network lifetime with different $δ$ .

GRMRP extension of network lifetime

Network lifetime can be defined as the time elapsed until the first node (or the last node) in the network depletes its energy.²³ Due to the deployment of highly redundant nodes, the death of one or more nodes in the dense area does not affect the monitoring quality of the network. In this article, lifetime of WSNs is defined as the period starting from the network deployment to the moment that network stops providing valuable information for the user, and two evaluation indexes of lifetime are given. The network lifetime $T_{popt}$ in the first method is defined as the running round when a given ratio of nodes fails and $T_{cover}$ in the second method is defined as the running round when the network coverage is not up to the predefined coverage. $T_{popt}$ and $T_{cover}$ are defined as follows

T_{popt} = \min {t : AN (t) \leq (1 - popt) \times N}

(15)

T_{cover} = \min {t : CN (t) \leq (1 - popt) \times N_{cluster}}

(16)

where $AN (t)$ indicates the number of alive nodes at round t and CN(t) indicates the number of valid coverage area at round t. If all the nodes in a given area die, the area is referred as invalid coverage area; otherwise, it is called valid coverage area.

For the sake of fair comparison, the value of data fusion rate c, the heterogeneous of node’s initial energy $E_{init}$ , and the differences in data acquisition capability $S_{data}$ of nodes are considered in this article. Besides, the energy consumption in the idle state is not considered in all protocols, and virtual grids are added to other protocols for comparison with $T_{cover}$ . The network lifetime is calculated from 50 randomly selected node deployment of the simulation. The scenario whose size is $100 m \times 100 m$ , total node number is 100, sink location is (50, 150) and the value of data fusion rate c is 0.5, is considered in this article.

Figure 5 shows the comparison of running rounds when the value of $E_{init}$ and $S_{data}$ are homogeneous. From Figure 5, it can be seen that the running rounds of DIRECT protocol increases with the increase in the number of failure nodes, while other protocols are relatively stable. Combining Figure 5(a) and (b), we can see that the average number of rounds of other protocols is generally improved, and the increase in GRMRP protocol is not obvious but has better performance than other protocols. From Figure 5, we can see that GRMRP has improved stability period by 200%–400% approximately as compared to other protocols such as LEACH, HEED, DEEC, and UCR, because the concept of basic cover unit is introduced to ensure network coverage and highly redundant of nodes are fully utilized using node dormancy mechanism. Overall, data fusion will reduce the network communication load, but to a certain extent will lead to premature death of nodes. Next, we consider the comparison of running rounds when the value of $E_{init}$ and $S_{data}$ are heterogeneous. The value of $E_{init}$ is set to five classes, namely, $E_{init}$ , $1.2 E_{init}$ , $1.4 E_{init}$ , $1.6 E_{init}$ , and $1.8 E_{init}$ , and each class accounted for 1/5.

Figure 5.

Comparison of running rounds when the value of E_init and S_data are homogeneous: (a) T_popt scheme and (b) T_cover scheme.

From Figure 6(a), it can be seen that the performance of running rounds in LEACH protocol changes little, while other protocols like HEED, UCR, and DEEC are significantly improved. Combining Figure 6(a) and (b), we can see that the average number of rounds of LEACH protocol is significantly improved using T_cover scheme, and the increase in GRMRP protocol is not obvious but has better performance than other protocols. Combining Figures 5 and 6, we can see that the performance of running rounds in GRMRP is stable and slightly improved whether using T_popt scheme or T_cover scheme, and this is because GRMRP takes into account the node energy factor and local energy information. Due to the limited space, only the homogeneity of energy and acquisition capacity is considered in subsequent section.

Figure 6.

Comparison of running rounds when the value of E_init and S_data are heterogeneous: (a) T_popt scheme and (b) T_cover scheme.

GRMRP energy consumption

In this part, we investigate the energy consumption of GRMRP. In total, 30 rounds of simulations are sampled and the amount of total energy spent by all nodes is shown in Figure 7. Figure 7 indicates the change in total energy consumption with the increase in network running, which exhibits a linear increasing effect. Since cluster heads send their packets to the sink via single hop and its distribution is stochastic in LEACH, and a large number of isolated clusters are produced inevitably, the variation of energy consumption of cluster heads in LEACH is drastic. In HEED, DEEC, and UCR, the number of cluster heads generated relatively stable and a small number of isolated cluster heads are generated, thus a considerable amount of system energy is saved. The cumulative effect of energy consumption consumed by nodes in GRMRP is much lower than that in other protocols, because multi-hop and node dormancy strategy which can reduce the traffic load each round and save energy by data forwarding. Due to the stability of cluster heads topology using the grid-based method in GRMRP, the amount of energy spent by cluster heads is almost the same in each round.

Figure 7.

Comparison of energy consumption.

GRMRP data latency

For the sake of fair comparison, data latency T_delay is defined as the maximum delay of data delivering to the sink. Serial data transmission scheme is adopted for data gathering in the cluster and data forwarding between the cluster heads, and parallel data transmission scheme is adopted for data delivering to the sink. T_delay is defined as follows

T_{delay} = \max {T_{intra}^{ch} (i) + T_{tosink}^{ch} (i)}

(17)

where $T_{intra}^{ch}$ indicates the latency of data collecting in the cluster and $T_{tosink}^{ch}$ indicates the latency of data forwarding to the sink. According to the definition of latency in Huynh et al.,⁶ the value of $T_{intra}^{ch}$ depends on the size of the member nodes in the cluster, that is, queuing time, and the value of $T_{tosink}^{ch}$ depends on the size of the data and data forwarding hops. The delay of one packet in a hop is adopted as the basic unit of latency for comparison.

Figure 8 shows the data forwarding latency comparison of DIRECT, LEACH, HEED, DEEC, UCR, and GRMRP. Greater data forwarding latency, in case of LEACH and UCR protocol, is due to greater data gathering delay in the cluster and greater data delivering to the sink. Due to the node dormancy mechanism, the delay $T_{intra}^{ch}$ of data acquisition in the cluster is reduced greatly. Although multi-hop strategy is adopted in GRMRP, the delay $T_{tosink}^{ch}$ in the routing phase is controlled effectively for the forwarding data size is relatively small.

Figure 8.

Comparison of data latency.

Comprehensive evaluation of performance

In order to evaluate the performance of the WSNs routing protocols objectively, a comprehensive index model is adopted for making up the one-sided nature of the single indicator evaluation model mentioned above.

In this section, we compare the five simulated routing protocols, namely, LEACH, DEEC, HEED, UCR, and GRMRP using monitoring efficiency and latency metrics. Monitoring efficiency is defined as the network lifetime in the case of ensuring network coverage in this article.

According to the comprehensive evaluation index system, we can solve the problem of how to evaluate the performance of protocol using the comprehensive score. Since WSNs routing protocol has very strong application-related characteristics, it is difficult to design a kind of evaluation indexes which can be used in various fields. In order to apply to different application scenarios, evaluating value of comprehensive performance can be calculated according to weighted average evaluation model which is proposed in this article. Assume a collection of different algorithms $A_{1}, A_{2}, \dots, A_{n'}$ , and suppose m′ evaluation indexes $I_{1}, I_{2}, \dots, I_{n'}$ are selected to evaluate these algorithms, we can obtain the following matrix

W = [\begin{matrix} w_{1, 1} & w_{1, 2} & \dots & w_{1, m'} \\ w_{2, 1} & w_{2, 2} & \dots & w_{2, m'} \\ ⋮ & ⋮ & ⋮ & ⋮ \\ w_{n', 1} & w_{n', 2} & \dots & w_{n', m'} \end{matrix}]

(18)

where $W_{i, j}$ denotes the score of protocol $A_{i}$ under the evaluation index $I_{j}$ ; $w_{i, j} (j = 1, 2, 3, \dots, m)$ denotes the weighted value of evaluation index and $w_{i, 1} + w_{i, 2} + \dots + w_{i, m'} = 1$ ; for fair comparison, the matrix W should eliminate the influence of the value of each evaluation index using the method of data transformation. The evaluation indexes are divided into two categories: one is positive index denoted by $C (I) = 1$ and the other is negative index denoted by $C (I) = 0$ . Positive index refers to the larger the measured value, the better the performance of the network. Negative index refers to the larger the measured value, the worse the performance of the network

w_{i, j}^{'} = {\begin{matrix} \frac{\frac{1}{n'} \sum_{i = 1}^{n'} w_{i, j}}{w_{i, j}} \begin{matrix} C (I_{j}) = 0 \end{matrix} \\ \frac{w_{i, j}}{\frac{1}{n'} \sum_{i = 1}^{n'} w_{i, j}} \begin{matrix} C (I_{j}) = 1 \end{matrix} \end{matrix}

(19)

To ensure the effectiveness and credibility of the comparison, we consider network lifetime under a given failure coverage using T_cover scheme. In this article, the given failure ratio used in the simulations is 30%. Applying formula (19) to W, we get matrix W′ as follows

W' = [\begin{matrix} \begin{matrix} v_{1, 1}^{'} & v_{1, 2}^{'} \\ v_{2, 1}^{'} & v_{2, 2}^{'} \\ v_{3, 1}^{'} & v_{3, 2}^{'} \end{matrix} \\ \begin{matrix} v_{4, 1}^{'} & v_{4, 2}^{'} \end{matrix} \\ \begin{matrix} v_{5, 1}^{'} & v_{5, 2}^{'} \end{matrix} \end{matrix}] \times [\begin{matrix} w_{I_{1}} \\ w_{I_{2}} \end{matrix}] = [\begin{matrix} \begin{matrix} \begin{matrix} 0.55 & 0.94 \\ 0.72 & 1.00 \\ 0.91 & 0.93 \end{matrix} \\ \begin{matrix} 1.01 & 0.73 \end{matrix} \end{matrix} \\ \begin{matrix} 1.82 & 2.05 \end{matrix} \end{matrix}] \times [\begin{matrix} w_{I_{1}} \\ w_{I_{2}} \end{matrix}]

(20)

where $I_{1}$ denotes the lifetime index and $I_{2}$ denotes the latency index. Due to the different objective of various protocols, we set two sets of weights, one is $I_{1} = I_{2} = 0.5$ , another is $I_{1} = 0.75$ , $I_{2} = 0.25$ . The comparison of the comprehensive evaluation score of the protocols is shown in Figure 9.

Figure 9.

Comprehensive evaluation score: (a) I₁=0.5, I₂=0.5 and (b) I₁=0.75, I₂=0.25.

Simulation results show that the comprehensive evaluation score of GRMRP is much better than the total score in the other protocols, thus we can infer that GRMRP has better performance in monitoring efficiency and data forwarding delay.

GRMRP reliable transmission

As mentioned in section “Basic cover unit formation,” despite that the nodes fall into each cluster with high probability, the fact is that there may exist the Energy Hole area where nodes are sparse. In the GRMRP protocol, the total number of neighbor relay cluster through which a source cluster can forward data toward the sink is maximum 8, and the details are illustrated in Figure 10. Assume the probability of denial of service of each adjacent cluster to be 0.5, hence the probability of at least one feasible data forwarding cluster of source cluster is $\geq (1 - {0.5}^{8}) = 99.6 %$ which is very high. If the source cluster is at any corner, the probability of connectivity is $\geq (1 - {0.5}^{3}) = 87.5 %$ which is also very high. Figure 10 indicates that Algorithm BCM-LF has good fault tolerance, and feasible forwarding clusters have been endowed with different forwarding priority such as Optimal, Level-2, Level-3, Level-4, and Level-5. Once the optimal forwarding area refuses to provide service of data forwarding, cluster head in source cluster uses greedy and perimeter forwarding strategy in Algorithm BCM-LF to find viable routing for data forwarding. It should be noted that the location of optimal relay cluster can be adjusted according to the location of the base station.

Figure 10.

Reliable transmission.

Conclusion

To mitigate the hot spot problem in LS-WSNs, we propose a GRMRP to balance the energy consumption among nodes. In GRMRP protocol, it should be noted that the number of grids is independent of the nodes’ distribution but closely related to the node transmission radius and node sensing radius. Once the node distribution is known, the number of initial cluster heads is determined and fixed. First, GRMRP divides the monitoring scenario into several virtual grids, where a virtual grid is a cluster. Then, the virtual grid is subdivided into several basic cover units, and only one node is kept in active state and other nodes go to sleep while still maintaining connectivity and coverage. GRMRP optimizes energy consumption among nodes in each grid by performing an ET-CHE strategy, combined with proactive round-robin rotation and passive adjustment. Furthermore, a bilateral consultative mechanism based on cluster head’s lifetime expectancy is presented for allocating data flow reasonably among clusters. Simulation results show that the GRMRP protocol effectively balances the energy consumption among nodes and achieves better monitoring performance, data forwarding delay, and significantly prolongs the network lifetime as compared to the existing WSNs routing protocols LEACH, HEED, DEEC, and UCR. Since we focus on evaluation index of the amount of data collection and the network lifetime, and consider the simplicity of the algorithm, much work on the protocol stability and scalability can be done in the future.

Footnotes

Acknowledgements

The authors are grateful to the anonymous referees for their insightful and valuable comments and suggestions.

Handling Editor: Muhammad Asim

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported in part by the National Natural Science Foundation of China under Grant 61170232 and 81160183, the research initiative Grant of Sun Yat-Sen University under Project 985, and Australian Research Council Discovery Project under Grant DP150104871.

References

Fei

Yang

et al . A survey of multi-objective optimization in wireless sensor networks: metrics, algorithms, and open problems. IEEE Commun Surv Tut 2017; 19(1): 550–586.

Curry

Smith

JC.

A survey of optimization algorithms for wireless sensor network lifetime maximization. Comput Ind Eng 2016; 101: 145–166.

Chen

Mukhopadhyay

Chuang

et al . Efficient coverage and connectivity preservation with load balance for wireless sensor networks. IEEE Sens J 2015; 15(1): 48–62.

Farman

Javed

Ahmad

et al . Grid-based hybrid network deployment approach for energy efficient wireless sensor networks. J Sens 2016; 16(3): 1–14.

Feng

et al . Reliable routing in wireless sensor networks based on coalitional game theory. IET Commun 2016; 10(9): 1027–1034.

Huynh

Dinh-Duc

Tran

CH.

Delay-constrained energy-efficient cluster-based multi-hop routing in wireless sensor networks. J Commun Netw 2016; 18(4): 580–588.

Jannu

Jana

PK.

A grid based clustering and routing algorithm for solving hot spot problem in wireless sensor networks. Wirel Netw 2016; 22(6): 1901–1916.

Kumar

Energy balanced position-based routing for lifetime maximization of wireless sensor networks. Ad Hoc Netw 2016; 52: 117–129.

Meng

Shi

Wang

et al . A grid-based reliable routing protocol for wireless sensor networks with randomly distributed clusters. Ad Hoc Netw 2016; 51: 47–61.

10.

Han

Qian

Jiang

et al . A grid-based joint routing and charging algorithm for industrial wireless rechargeable sensor networks. Comput Netw 2016; 101: 19–28.

11.

Soni

Mallick

DK.

A novel scheme to minimize hop count for GAF in wireless sensor networks: two-level GAF. J Comput Netw Commun 2015; 2015: 1–9.

12.

Jannu

Jana

. Energy efficient grid based clustering and routing algorithms for wireless sensor networks. In: Proceedings of the 4th international conference on communication systems and network technologies, Bhopal, India, 7–9 April 2014, pp.63–68. New York: IEEE.

13.

Yang

HEER—a delay-aware and energy-efficient routing protocol for wireless sensor networks. Comput Netw 2016; 104: 155–173.

14.

Ren

Zhang

et al . Lifetime and energy hole evolution analysis in data-gathering wireless sensor networks. IEEE T Ind Inform 2016; 12(2): 788–800.

15.

Madheswaran

Shanmugasundaram

RN.

Performance evaluation of balanced partitioning dynamic cluster head algorithm (BP-DCA) for wireless sensor networks. Wireless Pers Commun 2016; 89(1): 195–210.

16.

Zhang

Wang

Song

et al . A new clustering routing method based on PECE for WSN. EURASIP J Wirel Comm 2015; 2015(1): 1–13.

17.

Dong

Ota

Liu

et al . Joint optimization of lifetime and transport delay under reliability constraint wireless sensor networks. IEEE Trans Parallel Distrib Syst 2016; 27(1): 225–236.

18.

Enam

Qureshi

Misbahuddin

A uniform clustering mechanism for wireless sensor networks. Int J Distrib Sens N 2014; 2014: 1–14.

19.

Zarifzadeh

Yazdani

Nayyeri

Energy-efficient topology control in wireless ad hoc networks with selfish nodes. Comput Netw 2012; 56(2): 902–914.

20.

Guan

ZH.

Energy-aware routing in wireless sensor networks using local betweenness centrality. Int J Distrib Sens N 2013; 9(5): 307038.

21.

Zhang

Zheng

et al . An energy-balanced routing method based on forward-aware factor for wireless sensor networks. IEEE T Ind Inform 2014; 10(1): 766–773.

22.

Heinzelman

Chandrakasan

Balakrishnan

An application-specific protocol architecture for wireless microsensor networks. IEEE T Wirel Commun 2002; 1(4): 660–670.

23.

Younis

Fahmy

HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks. IEEE T Mobile Comput 2004; 3(4): 366–379.

24.

Heidemann

Estrin

. Geography-informed energy conservation for ad hoc routing. In: Proceedings of the 7th annual ACM/IEEE international conference on mobile computing and networking, Rome, 16–21 July 2001, pp.70–84. New York: ACM.

25.

Lindsey

Raghavendra

CS.

PEGASIS: power-efficient gathering in sensor information systems. Aerosp Conf Proc 2002; 3: 1125–1130.

26.

Qing

Zhu

Wang

Design of a distributed energy-efficient clustering algorithm for heterogeneous wireless sensor networks. Comput Commun 2006; 29(12): 2230–2237.

27.

Akbar

Javaid

Imran

et al . A multi-hop angular routing protocol for wireless sensor networks. Int J Distrib Sens N 2016; 12(9): 1–13.

28.

Chen

et al . An unequal cluster-based routing protocol in wireless sensor networks. Wirel Netw 2009; 15(2): 193–207.