Feifei Wang* | Haifeng Hu
OPEN ACCESS
The existing cluster routing protocols face common defects like uneven distribution of cluster heads and fast energy consumption. To solve these defects, this paper puts forward an energy-efficient cluster routing protocol, the ECRP. In this protocol, the energy of each node and its distance to the sending node are fully considered for cluster head selection and cluster formation. For intra-cluster routing, each cluster head determines its set of relay nodes and selects the relay nodes on its route to the sink node according to the minimum hop-count algorithm and the residual energy of each node. The simulation results show that the ECRP clearly outperformed the classic algorithms in network load balancing, node energy consumption, and WSN lifecycle.
cluster routing, energy-efficient, transfer nodes, load balancing
The wireless sensor network (WSN) can sense, collect and process the information of objects in its monitoring area. However, the network performs poorly in terms of storage and wireless capacity, due to the limited size and energy of sensor nodes. Therefore, the primary goal of routing design and improvement is to organize sensor nodes in such a manner that collects data and sends them to the sink node with limited energy, and thus prolongs the network lifecycle. Since planar routing faces difficulty in delay control and only suits small networks, the cluster routing has been the hotspot in the research of routing protocols [1-4].
Zhao et al. [5] puts forward an energy-efficient opportunistic routing protocol, which selects the route based on the ratio of residual energy of each node to the expected cost. Sun et al. [6] develops a distributed cluster routing protocol based on dynamic partitioning and load balancing, aiming to solve the “hot spot” problem caused by load imbalance between network nodes. Peng et al. [7] designs a cluster routing mechanism, in which multiple heads are selected from each cluster to transmit data together. Considering the energy and position of each node, Hu and Xiao [8] proposes a novel energy-balanced multi-hop routing algorithm that overcomes two problems with the low-energy adaptive clustering hierarchy (LEACH) algorithm, namely, the irrational selection of cluster heads, and the excessive energy consumption on the routes between some heads and the base station. The above cluster routing algorithms partially increase the energy utilization of network nodes, but still have common defects like unreasonable cluster structure, long delay of data transmission and route load imbalance.
To eliminate these defects, this paper presents an improved energy-efficient cluster routing protocol (ECRP), drawing on the merits of existing cluster routing algorithms. The ECRP introduces the actual information emission radius and current energy of network nodes to the selection of cluster heads. During cluster formation, each common node joins the most suitable cluster, based on the energy of each node and its distance to the sending node. The inter-cluster routes are constructed in the light of the minimum hop-count algorithm and the residual energy of each node. The ECRP can form a reasonable cluster structure and partially balance the energy consumption between nodes [9-12].
The remainder of this paper is organized as follows: Section 2 introduces classic routing protocols, and explains the network model and communication model; Section 3 describes the ECRP, highlighting the workflow and algorithm principle; Section 4 compares the ECRP with the LEACH and the hybrid energy efficient distributed clustering (HEED) through simulation; Section 5 sums up the main contributions of this research.
2.1 Classic routing protocol
Many algorithms have emerged in the research of WSN cluster routing protocols. The most typical ones include the LEACH [13], the HEED [14] and the power-efficient gathering in sensor information systems (PEGASIS) [15]. Almost all WSN cluster routing algorithms are extended from these three classical algorithms. The LEACH is the earliest cluster routing protocol for the WSN. This protocol introduces the concept of “round”, such that the cluster routing can be implemented periodically. During the selection of cluster heads, the probability for a node to be selected depends on whether it has been selected as cluster head before. If not, the probability for this node to be selected, T(n), can be computed as:
$T(n)=\left\{ \begin{align} & \frac{\text{p}}{1-p\text{ }[r\bmod \text{ }(1/p)]}\text{ }if\text{ }n\in G \\ & 0\text{ otherwise} \\\end{align} \right.$ (1)
The node produces a random number between 0 and 1. If the number is smaller than T(n), the node will become a cluster head, and broadcast this information across the network. Each common node may receive the information from multiple cluster heads. Then, the common node will decide to join the cluster of the head with the strongest signal, and send its decision to this cluster head. Upon receiving the decision, the cluster head will transmit the time slots via time-division multiple access (TDMA) and codes via code- division multiple access (CDMA). After the data have been transmitted for a period, the next round of clustering will be initiated.
Compared with the previous protocols, the LEACH protocol enjoys an excellent performance. But this protocol still has several shortcomings: the cluster heads are selected randomly and distributed unevenly, and the clusters are formed too frequently. Therefore, the LEACH has been improved into the PEGASIS and the HEED. In the PEGASIS, the nodes are grouped into a communication chain by the greedy algorithm, and take turns to serve as the only cluster head of the network. In this way, the cluster head is selected much less frequently. However, the unique cluster head, coupled with the chained mode, brings a high risk to data transmission, and increases the transmission delay. Meanwhile, the HEED computes the probability of being selected as the cluster head (CHprob) by:
$C{{H}_{prob}}=\max (C{}_{prob}\times \frac{{{E}_{residual}}}{{{E}_{\max }}},{{P}_{\min }})$ (2)
The cluster heads are generated after several iterations. On the upside, the HEED considers the residual energy of each node and the intra-cluster communication overhead. On the downside, this algorithm only applies to the scenario in which all network nodes have the same initial energy, faces difficulty in the setting of the CHprob threshold (Pmin), and pushes up the probability of independent cluster heads.
2.2 Network model and communication model
Let M*M be the monitoring range of the WSN and N be the number of sensor nodes. Each node needs to collect and transmit data based on a certain algorithm. The WSN is assumed to satisfy the following conditions: (1) The sink node remains at a fixed position outside the monitoring area, and the position of any node will not change except for death; (2) The sensor nodes are of the same structure and capable of data fusion; (3) The channels are symmetric, and the distance between any node and the sending node can be approximated based on the received signal strength indicator (RSSI), provided that the transmitting power is known; (4) Each node can communicate with the sink node directly or indirectly in a single-hop or multi-hop manner.
The ECRP adopts the same wireless communication model as the LEACH. The energy consumed by a network node transmits kbit data to a node or sink node over the distance of d can be computed by:
${{E}_{Tx}}(k,d)=\left\{ \begin{align} & k*{{E}_{elec}}+k*{{\xi }_{fs}}*{{d}^{2}}\text{ }d<{{d}_{0}} \\ & k*{{E}_{elec}}+k*{{\xi }_{amp}}*{{d}^{4}}\text{ }d\ge {{d}_{0}} \\\end{align} \right.$ (3)
The energy consumed to receive the kbit data can be computed by:
${{E}_{Rx}}(k)=k*{{E}_{elec}}$ (4)
The above formulas show that the energy consumption of data transmission is related to the distance d. The channel model varies with the distances. If d<d0, the energy consumption is positively correlated with the square of the distance; if d>d0, the energy consumption is positively correlated with the fourth power of the distance. It can also be seen that the energy consumption of data reception depends on the amount of data being transmitted, because the receiving node needs to fuse the data before forwarding them to the other nodes.
The ECRP was improved from the classic cluster routing protocols in terms of cluster head selection, cluster formation, and the routing for data transmission. Unlike the LEACH, the ECRP does not need to re-cluster the nodes in each round. Instead, a node energy prediction mechanism was introduced to judge when to cluster. Whether to re-cluster at a moment is judged by the predicted energy of the cluster head at that moment. Specifically, the energy prediction model in Li et al. [16] was adopted to predict the residual energy of each node after two rounds, laying the basis for judging the necessity of re-clustering.
3.1 Cluster head selection and cluster formation
The first step of cluster head selection is to determine the number of clusters in the network. In our network model, the ideal number and the information emission radius of cluster heads in the network can be respectively obtained by:
${{k}_{opt}}=\frac{\sqrt{N}}{\sqrt{2\pi }}\sqrt{\frac{{{\xi }_{fs}}}{{{\xi }_{amp}}}}\frac{M}{{{d}^{2}}_{toBS}}$ (5)
$R=\sqrt[4]{\frac{2\pi }{N}}\sqrt[4]{\frac{{{\xi }_{amp}}}{{{\xi }_{fs}}}}\sqrt{M}{{d}_{toBS}}$ (6)
The above values are obtained under ideal conditions. In the actual environment, the ideal values may lead to coverage holes and hinder the connections within the network. Hence, the information emission radius in actual operations must be greater than R, and should be obtained through software simulation.
The next step is to select the cluster heads. The node energy is the primary concern of cluster head selection, because each cluster head needs to receive, fuse and transmit data. Each network node Si (i=1~N) generates a number Si.T based on its residual energy Eresudial. Since Si.T=T*1/[arctan(Si.Eresudial)+1], a node with a high residual energy will output a smaller number than that with a low residual energy. At the beginning of each round, all nodes are candidate cluster heads. Then, the countdown is started, and each candidate will send information within its information emission radius R. A candidate will be selected as cluster head if it has not received any information from the other nodes before the end of the countdown, and as a common node if otherwise.
Once the cluster heads are selected, the cluster formation will begin. Firstly, each cluster head sends a message containing its energy, unique ID and signal label. Each common node may receive the messages from multiple cluster heads, and must select a suitable cluster based on the clustering algorithm. Firstly, the node should compute its distance to a cluster head (d) based on the RSSI. If the distance to the cluster head with the highest energy is smaller than d0 in formula (3), then the node should enter the cluster of that head. If d>d0, the node should join the cluster of the head with the maximum value obtained by α*Ecurrent+(1-α)*(1-arctan(d)*2/π). Next, the node will send a request to the head of the preferred cluster. After cluster formation, each cluster head will allocate the time slots according to the number of cluster members and send them to the members via TDMA. The workflow of cluster head selection and cluster formation is illustrated in Figure 1 below.
Figure 1. The workflow of cluster head selection and cluster formation of the ECRP
3.2 Routing
In each cluster, the members need to send the collected information to the cluster head. During the cluster formation, the node-head distance has been considered. Therefore, the intra-cluster communication can be directly implemented, i.e. all members can transmit data in one hop to the cluster head. Then, the cluster head will fuse the received data and send the fused data to the sink node. Since the cluster heads spread across the network, the single-hop communication is not suitable for the data transmission between cluster heads and the sink node. In this communication mode, the cluster heads far away from the sink node will soon die of energy depletion. Hence, the intra-cluster communication should be implemented by multi-hop routing.
Based on the energy consumed for a node to send and receive data (formulas (3) and (4)), the energy consumed for node SNi to directly communicate with the sink node can be computed by:
${{E}_{\text{toSink}}}={{E}_{elec}}*k+{{\xi }_{amp}}*k*{{d}^{2}}(S{{N}_{i}},S\text{ink})$ (7)
Suppose SNi transmits data to the sink node through the relay node SNj, that is, the data from SNi are fused by SNj before being sent to the sink node. In this case, the energy consumed to transmit the data from SNi to the sink node can be computed by:
$\begin{align} & {{E}_{\text{total}}}=E(S{{N}_{i}},S{{N}_{j}})+E(S{{N}_{j}},\operatorname{Sin}k)+E(S{{N}_{j}}) \\ & ={{E}_{elec}}*k+{{\xi }_{amp}}*k*{{d}^{2}}(S{{N}_{i}},S{{N}_{j}})+{{E}_{elec}}*k+{{\xi }_{amp}}*k*{{d}^{2}}(S{{N}_{j}},\operatorname{Sin}k)+{{E}_{elec}}*k \\ & =3*{{E}_{elec}}*k+{{\xi }_{amp}}*k*\left[ {{d}^{2}}(S{{N}_{i}},S{{N}_{j}})+{{d}^{2}}(S{{N}_{j}},\operatorname{Sin}k) \right] \\\end{align}$(8)
Thus, the energy consumption mainly depends on d2(SNi,Sink) and d2(SNi,SNj)+d2(SNj,Sink). Less energy is consumed only if the following formula is valid:
${{d}^{2}}(S{{N}_{i}},S{{N}_{j}})+{{d}^{2}}(S{{N}_{j}},\operatorname{Sin}k)$<${{d}^{2}}(S{{N}_{i}},S\text{ink})$ (9)
Note that the reduction of energy consumption should be pursued without too many hops. Otherwise, the data transmission will face serious delays. The routing principle can be summed up as follows:
Firstly, the sink node broadcasts a message within its information emission radius d0. The message contains the number of hops (Hop_count), which is initialized as zero. Upon receiving the message, a cluster head will add 1 to the Hop_count, include the sink node to its set of relay cluster heads, and then forward the message (containing the Hop_count and the residual energy of the node).
Meanwhile, the cluster heads whose distance to the sink node is greater than d0 cannot receive the message directly from the sink node. Upon receiving the message from another cluster head, such a far away cluster head will add 1 to the Hop_count, and compare the new Hop_count with its original Hop_count. If the original Hop_count is greater, then the far away cluster head will update its number of hops as Hop_count+1 and add the cluster head sending the message into its set of relay cluster heads. Then, the far away cluster head will forward the message. Otherwise, the far away cluster head will not update its number of hops.
In this way, each cluster head can obtain the minimum number of hops to the sink node and a set of relay cluster heads. During data transmission, each cluster head will select a node satisfying formula (9) out of its set of relay cluster heads to serve as the relay node. If more than one node satisfy formula (9), the node with the highest energy will be selected as the relay node. This principle can minimize the time delay while reducing the energy consumption. Moreover, no node needs to frequently forward data, because the relay node is selected dynamically for each transmission. Thus, the network is less likely to have coverage holes.
The ECRP was compared with classic protocols like the LEACH and the HEED through OMNeT++simulation.
4.1 Parameter setting
Table 1 lists the simulation parameters.
|
Parameter |
Value |
|
Network coverage |
(0,0)~(200,200) |
|
Position of sink node |
(100, 250) |
|
Total number of nodes |
400 |
|
Initial node energy |
0.5J |
|
Eelec |
50nJ/bit |
|
ξfs |
10pJ/bit/m2 |
|
ξamp |
0.0013pJ/bit/m4 |
|
d0 |
87m |
|
EDA |
5nJ/bit/signal |
|
Data packet size |
4000bits |
The simulation mainly focuses on the actual information emission radius k, the network load balance factor (LBF), the variation of network residual energy with the number of rounds, and the variation of the surviving nodes with the number of rounds.
Figure 2. The round of the first death vs. information emission radius
The actual information emission radius of each node should surpass the ideal radius in formula (6), aiming to ensure inter-cluster communication, eliminate coverage holes and prevent independent cluster heads. In other words, the value of k in the formula of actual information emission radius Rac=k*R should be greater than one. As shown in Figure 2, the first death appeared the latest when k equals 1.6. Thus, the k value was set to 1.6 for the ECRP.
Considering the impacts of the number of cluster members on the rationality of cluster structure, the energy consumption of cluster head and the lifecycle of the WSN, the LBF was introduced to evaluate the performance of each protocol:
$LBF=\frac{{{n}_{c}}}{\sum\limits_{i=1}^{{{n}_{c}}}{{{({{x}_{i}}-u)}^{2}}}}$ (10)
Figure 3. The LBFs of the three protocols
As shown in Figure 3, the LEACH had the smallest LBF, due to its defects in cluster head selection and cluster formation; the HEED had a relatively large LBF, thanks to its improvement to the LEACH; the ECRP boasted the largest LBF, and thus the best load balance. The superiority of the ECRP is attributable to two factors: (1) the actual information emission radius of each node is verified before cluster head selection; (2) the node-sink distance is considered for cluster head selection and cluster formation. The two factors limit the number of cluster members, rationalize the cluster structure, and reduce the energy consumed for a common node to communicate with the cluster head.
Figure 4. The variation of network residual energy with the number of rounds
As shown in Figure 4, the common nodes of the ECRP consumed less energy in cluster formation and intra-cluster communication than those of the LEACH and the HEED, and the cluster heads of the ECRP were more energy-efficient than their counterparts of the other two protocols. The energy efficiency of the ECRP can be explained as follows: In the ECRP, the energy of each node and its distance to the sending node before selecting the cluster heads and clustering the network nodes; During cluster formation, the information is sent within the actual information emission radius; The cluster heads transmit data to each other via the multi-hop routes with the minimum number of hops; The data are fused before being transmitted.
Figure 5. The variation of the surviving nodes with the number of rounds
As shown in Figure 5, the network nodes of the ECRP survived for longer time than those of the LEACH and the HEED. The possible reason of the result is as follows: The ECRP always operates based on the energy of each node and its distance to the sending node. Under this protocol, the first death and last death both occur later than the other protocols, which effectively extends the lifecycle of the network. Besides, the first death and last death are separated by only a few rounds, which partially balances the energy consumption of network nodes.
This paper proposes an energy-efficient cluster routing protocol, the ECRP, based on the LEACH and the HEED, aiming to solve the defects of these classic cluster routing protocols. To eliminate coverage holes, prevent independent cluster heads and slowdown node deaths, the energy of each node and its distance to the sending node were fully considered before selecting cluster heads, clustering network nodes and setting up routes for data transmission. The simulation results show that the ECRP can output clusters of rational structures, effectively balance the network load, extend the lifecycle of the network, and enhance the utilization of nodes.
The Science and Technology Project of Pingdingshan City: The Research on Home Care Service Platform Based on Internet of Things Technology, 201700812.
[1] Singh, A., Rathkanthiwar, S., Kakde, S. (2016). Energy efficient routing of WSN using particle swarm optimization and V-LEACH protocol. 2016 International Conference on Communication and Signal Processing (ICCSP), Melmaruvathur, India. https://doi.org/10.1109/ICCSP.2016.7754544
[2] Attea, B.A., Khalil, E.A. (2012). A new evolutionary based routing protocol for clustered heterogeneous wireless sensor networks. Applied Soft Computing, 12(7): 1950-1957. https://doi.org/10.1016/j.asoc.2011.04.007
[3] Zhang, S.Q., Tao, Y., Dai, J.J. (2019). Multi-hop clustering routing protocol for energy harvesting wireless sensor networks. Computer Engineering and Design, 40(3): 611-616, 622. http://dx.chinadoi.cn/10.16208/j.issn1000-7024.2019.03.003
[4] Barati, H., Movaghar, A., Rahmani, A.M. (2015). EACHP: Energy aware clustering hierarchy protocol for large scale wireless sensor networks. Wireless Personal Communications, 85(3): 765-789. https://doi.org/10.1007/s11277-015-2807-2
[5] Zhao, M., Kumar, A., Chong, P.H.J., Lu, R.X. (2017). A reliable and energy-efficient opportunistic routing protocol for dense lossy networks. IEEE Wireless Communications Letters, 6(1): 26-29. https://doi.org/10.1109/LWC.2016.2625279
[6] Sun, Y.Q., Peng, J., Liu, T., Chen, X.H. (2014). Uneven clustering routing protocol based on dynamic partition for wireless sensor network. Journal on Communications, 35(1): 198-206. http://dx.chinadoi.cn/10.3969/j.issn.1000-436x.2014.01.023
[7] Peng, S., Wang, T., Low, C.P. (2015). Energy neutral clustering for energy harvesting wireless sensors networks. Ad Hoc Networks, 28: 1-16. https://doi.org/10.1016/j.adhoc.2015.01.004
[8] Hu, F.S., Xiao, Q. (2014). Multi-hop routing algorithm of eenergy-balancing based on LEACH. Journal of Chinese Computer Systems, 35(1): 70-73. http://dx.chinadoi.cn/10.3969/j.issn.1000-1220.2014.01. 014
[9] Arumugam, G.S., Ponnuchamy, T. (2015). EE-LEACH: Development of energy-efficient LEACH Protocol for data gathering in WSN. EURASIP Journal on Wireless Communications and Networking, (1): 76. https://doi.org/10.1186/s13638-015-0306-5
[10] Ying, K.Z., Yang, Z.K., Zhou, X.N., Mao, K.J., Chen, Q.Z. (2018). A controllable cluster scale energy equalization routing protocol. Chinese Journal of Sensors and Actuators, 31(3): 429-435. http://dx.chinadoi.cn/10.3969/j.issn.1004-1699.2018.03.018
[11] Liao, F., Zhang, W. (2017). Uneven clustering routing protocol based on minimum spanning tree. Chinese Journal of Sensors and Actuators, 30(9): 1412-1416. http://dx.chinadoi.cn/10.3969/j.issn.1004-1699.2017.09.019.
[12] Pan, J.Q., Feng, Y.Z. (2018). Improved LEACH clustering routing algorithm of sensor network. Journal of Jilin University (Science Edition), 56(6): 1476-1482.
[13] Heinzelman, W.B., Chandrakasan, A.P., Balakrishnan, H. (2002). An application- specific protocol architecture for wireless microsensor networks. IEEE Transactions on Wireless Communications, 1(4): 660-670. https://doi.org/10.1109/TWC.2002.804190
[14] Younis, O., Fahmy, S. (2004). HEED: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks. IEEE Transactions on Mobile Computing, 3(4): 366-379. https://doi.org/10.1109/TMC.2004.41
[15] Lindsey, S., Raghavendra, C.S. (2002). PEGASIS: Power efficient gathering in sensor information systems. Proceedings, IEEE Aerospace Conference, Big Sky, MT, USA, USA. https://doi.org/10.1109/AERO.2002.1035242
[16] Li, J., Li, Z.Y., Wang, R.C. (2009). A coverage-preserving node scheduling scheme based on energy prediction in wireless sensor networks. Journal of Nanjing University of Posts and Telecommunications (Natural Science Edition), 29(2): 16-21.
