Wireless sensor networks routing algorithm based on block clustering and springboard nodes

LIU Yuhong， FU Fuxiang， LI Cuiran

(School of Electronic and Information Engineering， Lanzhou Jiaotong University， Lanzhou 730070， China)

Abstract： In the wireless sensor networks (WSN), the sensor nodes have limited battery life and are deployed in hostile environments. It is very difficult to recharging or replacement of the batteries after deployment for the sensor nodes in inaccessible areas. Therefore, how to increase the network lifetime of the WSN is deserved to be studied. In this study, a WSN routing algorithm was proposed based on block clustering and springboard nodes to increase the network lifetime of the WSN. Firstly, by analyzing the influence of communication transmission distance on network energy consumption, block clustering was introduced to control node transmission distance in order to reduce total network energy consumption. In addition, a network transmission model was proposed based on springboard nodes and the advantages of network energy consumption of this model against multi-hop between clusters were analyzed. The simulation results show that, compared with the LEACH algorithm, EECPK-means algorithm and energy centroid clustering algorithm, the proposed routing algorithm effectively prolongs the network lifetime of WSN.

Key words： wireless sensor networks (WSN)； network lifetime； springboard node； block clustering

0 Introduction

In recent times, wireless sensor networks (WSN) have been widely used in various fields such as environment monitoring, healthcare, industrial automation and target tracking[1-5]. WSN have many advantages including self-configuration, flexible networking, cost-effectiveness and small size. However, the energy of sensor nodes is limited, and the sensor nodes are often deployed in harsh and unattended environments[6]. Once the energy of the node is exhausted, it is difficult to be replenished in time. Therefore, it has become vital topics to reduce energy consumption and extend the network lifetime in WSN research[7]. Clustering is one of the important methods for this problem[8]. The entire network is divided into a number of clusters, where one of the sensor nodes is selected as the cluster head. The cluster head is responsible for communication within and outside the cluster. The communication within the cluster is called intra-cluster communication, where cluster member sends data to the cluster head. The communication between the cluster heads and the base station (BS) is called inter-cluster communication. Finally, sensed environment data by the sensor nodes is transferred to sink node via the cluster head sensor nodes. To improve energy efficiency and network lifetime, many researchers have proposed corresponding algorithms.

HEINZELMAN W R et al. proposed the LEACH algorithm[9]. Its execution process is cycled with “rounds”. Random initialization of cluster heads in each round ensures that each node acts as a cluster head with equal probability, so that the nodes in the network consume similar energy to an extent. However, the nodes far away from the cluster head exhaust their energy prematurely because of sending data over a long distance. Besides, the load of the cluster head nodes is extremely unbalanced. RAY A and DE D proposed the EECPK-means algorithm[10]. This algorithm improves the k-means clustering algorithm. Firstly, set the initial cluster heads according to the midpoint initialization algorithm. Then, calculate the final cluster heads according to thek-means algorithm. The EECPK-means algorithm balances the number of member nodes in each cluster to a certain extent. However, after the initial cluster head is set, the remaining energy of each node is not considered. EECPK-means algorithm only considers the remaining energy of the final cluster head. Besides, iterative operations increase the burden of the network. LOGANATHAN S et al. proposed an energy centroid clustering algorithm[11]. After the cluster is formed, this algorithm determines the final cluster head according to the remaining cluster heads, energy centroids and energy threshold to reduce network energy consumption. However, the cluster head closer to the BS not only is responsible for the communication of data in the cluster but also forwards the data of the cluster head far away from the BS[11], which caused uneven energy consumption of the cluster head and thus affecting the network life.

Based on the analysis of the above documents, a WSN routing algorithm based on block clustering and springboard nodes was proposed to improve the network life in this study. Firstly, the monitoring area is divided into several blocks according to block clustering. In each block, the sending distance between nodes does not exceed the distance threshold. Then, the springboard nodes are introduced to forward the data of the cluster heads to the BS to balance the energy consumption of the cluster head. In the cluster head election, the remaining energy of each node is fully considered, and the node with the largest remaining energy is elected as the cluster head. Finally, simulation experiments and comparative analysis are carried out to verify the effectiveness of the proposed routing algorithm in network lifetime improvement.

1 Basic model and parameter settings

1.1 Radio energy model

The energy consumption of sensor nodes is mainly focused on receiving and sending sensor data, so that the energy analysis of sensor nodes in this study mainly considers the radio power consumption of the each node[12]. The energy consumption of a node sending data of l bit to a node at a distancedis expressed as

ETX(l,d)=ETX-elec(l)+ETX-amp(l,d),

(1)

whereETX-elecis the energy consumption of the transmitting circuit, andETX-ampis the transmission dissipation energy.

Ifd≤Dthreshold, there is

ETX(l,d)=lEelec+lεfsd2,

(2)

and ifd>Dthreshold, there is

ETX(l,d)=lEelec+lεmpd4,

(3)

where the distance thresholdDthreshold[13]can be expressed as

(4)

The energy consumption of nodes receivinglbit data is expressed as

ERX(l)=lEelec.

(5)

1.2 Network model

For the network model,some assumptions are acquired in the proposed network.

1) The sensor nodes are randomly distributed. Once the nodes are deployed, the position of each node is fixed.

2) Each sensor node is homogeneous and has the same and limited initial energy.

3) BS energy can be replenished, so it is assumed that the BS energy is infinite.

4) After the nodes are deployed, the BS has the location of each node.

5) All the sensor nodes have unique ID numbers, respectively.

1.3 Parameters

In the process of analyzing energy consumption and simulation, the parameters and corresponding values are shown in Table 1.

Table 1 Parameters settings

2 Analysis of energy consumption

2.1 Influence of transmission distance on energy consumption

The ordinary sensor node is responsible for collecting sensing data and sending the collected data to the cluster head node. According to Eqs.(2) and (3), it is shown that the energy consumption of a node sending l bit data is proportional to the distance at which the node sends the data. According to Ref.[11], if the sending distance of the node is less than or equal toDthreshold, a free space model is used. If the sending distance is greater thanDthreshold, a multi-pass fading space model is used. The effect of sending distance on the energy consumption and dissipation energy of the node when sending l bit data are shown in Fig.1. It can be seen that when the transmission distance is less thanDthreshold, the dissipation energy increases slowly and the dissipation energy increases sharply otherwise.

Fig.1 Energy and dissipated energy required by a node to send 1 bit data

Therefore, it can effectively reduce unnecessary energy dissipation by making the distance between the node and the communication cluster head less than theDthreshold. In this study, block clustering was proposed to ensure that the communication distance is stable within the distance threshold.

2.2 Energy consumption analysis of springboard nodes

In wireless sensor network communication, multi-hop communication among clusters is usually used to forward the data of the cluster head to the BS when the cluster head node far away from the BS communicates with the BS. However, it increases the burden of the cluster heads that are closer to the BS, resulting in unbalanced load on the cluster heads. In this study, springboard nodes were proposed to forward the data of the cluster head node far away from the BS to the BS. The cluster head node transmits the data to the BS through the springboard nodes without increasing the burden of the cluster head near the BS. Besides, the energy consumption of using springboard nodes is also less than that using multi-hop among clusters. Next, the specific proof is carried out.

Assume that both the numbers of nodes in cluster 1 and cluster 2 aren. If the multi-hop among clusters is used, cluster head 1 collects the data in cluster 1 and sends the data to cluster head 2 firstly, and then cluster head 2 transmits the data in cluster 2 and the data sent by cluster head 1 to the BS secondly, as shown in Fig.2. In the above method, the energy consumption of cluster head 1 can be expressed as

E1,m=E1,RX+E1,TX=

(6)

Fig.2 Path model of springboard node and inter-cluster multi-hop

Cluster head 2 not only is responsible for receiving and sending data in cluster 2, but also forwards data sent by cluster head 1 to the BS. The energy consumption of cluster head 2 can be expressed as

E2,m=E2,RX+E2,TX+E2，RT=

(7)

Adding Eqs.(6) and (7), it is indicated that when using multi-hop between clusters, the total energy consumption is obtained by

Esum,m=E1,m+E2,m=6nlEelec+

(8)

If the springboard node is used to forward data, cluster head 1 collects data in cluster 1 and the springboard node (S) is only responsible for forwarding the data sent by cluster head 1 to the BS, while cluster head 2 is only responsible for forwarding data in the cluster, as shown in Fig.2. In this method, the energy consumption of cluster head 1 can be expressed as

(9)

In this way, cluster head 2 is only responsible for transmitting the data in cluster 2 without forwarding the data of the cluster head 1. The energy consumption of cluster head 2 can be expressed as

(10)

The node closest to the midpoint between cluster head 1 and BS is selected as the springboard node. As shown in the Fig.2, the springboard node is named as S node ands1=s2=d3/2. The S node is responsible for forwarding the data of cluster head 1. The energy consumption of the S node can be expressed as

(11)

Combining Eqs.(9)-(11), it is indicated that when the springboard node is used, the total energy consumption can be obtained by

Esum,s=E1,s+E2,s+ES=6nlEelec+

(12)

Subtracting Eq.(12) from Eq.(8), there is

(13)

According to the triangle cosine theorem, there is

(14)

According to Eq.(14), compared with multi-hop between clusters, the use of springboard node can effectively reduce the energy consumption of cluster head communication. According to Eqs.(6)-(7), when the multi-hop among clusters is adopted, the energy consumption of cluster head 2 is greater than that of cluster head 1, resulting in unbalanced energy consumption of cluster heads. According to Eqs.(9)-(11), when springboard nodes are used, the energy consumption of cluster head nodes and springboard nodes is basically the same, which balances the energy consumption of each cluster head.

3 Wireless sensor network routing algorithm

3.1 Nodes deployment

In this study, nodes are randomly deployed in a square area. After the node is deployed, the locations are determined. The location of the node is given by

(15)

According to Eq.(15), some samples of randomly distributed node locations can be gotten. Relative node samples are used to compare different algorithms for the sake of fairness in the simulation experiment.

3.2 Block division

In this study, the monitoring area was divided into several blocks according to the distribution of nodes. The sensor nodes in each block only communicate with the cluster head nodes in that block. Next, the block division process will be described in detail.

Firstly, with BS as the center, nodes whose distance from BS is less thanDthresholdare divided into block 1, and other nodes are divided into block 2, as shown in Fig.3.

Fig.3 Partitioning for the first time

The distance between the node in block 1 and the BS is small, and the node can directly communicate with the BS. The cluster head elected in block 2 selects the springboard node in block 1, and springboard node is responsible for forwarding data. The node farthest from the BS in block 2 is assumed to be at location (100,100). If this node is elected as the cluster head, the midpoint position between it and the BS should be (50,50). The distance between midpoint and the node located at (100,100) is about 70.7

Then, subdivide block 2. Assume that the farthest distance between nodes in block 2 isdmax, block 2 is divided intomblocks, and the value ofmis defined by

(16)

As shown in Fig.4, according to the two nodesaandbthat are the farthest nodes in block 2,mis calculated. Assume that the number of nodes in block 2 isnb2andm=3, thenb2/mnodes closest to pointain block 2 are allocated to block 2.1. Similarly, thenb2/mnodes closest to pointbare allocated to block 2.2, and the remaining nodes are allocated to block 2.3. This ensures that the farthest distance among nodes in each block is less thanDthreshold, and the number of nodes in each sub-block isnb2/m, which can well balance the load energy consumption of each cluster.

Fig.4 Partitioning for the second time

3.3 Select cluster heads and springboard nodes

As the sensor nodes in block 1 are closer to the BS, they can communicate directly with the BS. In block 2, a cluster head is selected in each sub-block, which is responsible for receiving and sending data in this block. In the first round, because the energy of each node is the initial energyE0, the node closest to the center of the block is directly selected as the cluster head. In the second round and later, the node with the highest energy in the block is selected as the cluster head node. The centroid of the block is calculated by

(17)

In this way, the number of cluster heads can be optimized tonch, which can be expressed as

(18)

Once the cluster head nodes are selected, the locations of midpoints between cluster head nodes and BS are set and the node closest to the midpoint is selected as the springboard node, which is responsible for forwarding the data of the cluster head to the BS, of the cluster head in block 1.

4 Simulation and discussion

In order to evaluate the performance of the proposed routing algorithm, a simulation environment is built by using MATLAB simulation tool. Under the same node locations, the proposed routing algorithm, LEACH algorithm, EECPK-means algorithm and energy centroid clustering algorithm are compared and analyzed. The parameters used are given in Table 1.

Firstly, according to Eq.(15), the nodes are randomly initialized in theM×Msquare monitoring area. The position of the node after initialization is shown in Fig.5.

Fig.5 Sensor nodes deployment

Then, the sensor nodes are partitioned according to the block clustering proposed in Section 3.2, as shown in Fig.6. The number of nodes in each cluster in block 2 is approximately the same.

Fig.6 Block division

In addition, the number of member nodes of each cluster head was compared by using the three algorithms (the proposed routing algorithm, EECPK-means algorithm and energy centroid algorithm) under four randomly generated node samples (sample 1, sample 2, sample 3 and sample 4), as shown in Table 2. To be more intuitive, the variance of the number of member nodes in the cluster is compared, as shown in Fig.7.

Fig.7 Comparison of variance of number of member nodes

The variance of the number of member nodes in the proposed routing algorithm is less than 0.57 and the maximum variance of the number of member nodes in the energy centroid algorithm is 5.22, and the maximum variance of the number of member nodes in the EECPK-means algorithm is 6.32. It is shown that the proposed routing algorithm can effectively balance the number of member nodes of each cluster head. According to Table 2, it is indicated that the number of member nodes of each cluster head in the proposed routing algorithm is half of that of EEPCK-means algorithm and energy centroid clustering algorithm, which greatly increases the service life of the cluster head.

Table 2 Number of member nodes

Finally, the network lifetime of the proposed routing algorithm, LEACH algorithm, EECPK-means algorithm and Energy centroid clustering algorithm is simulated and compared. Under four various node samples (sample 1, sample 2, sample 3 and sample 4), the number of surviving nodes of four algorithms with time is shown in Fig.8. Specifically, Table 3 shows the network lifetime of the four algorithms under four different node samples. It can be found that the proposed routing algorithm has an average improvement of 12.03%, 19.91% and 165.84% higher over the Energy centroid clustering algorithm, EECPK algorithm and LEACH algorithm in terms of the network lifetime. It can be found that the proposed routing algorithm can prolong network life compared to the other algorithms.

Table 3 Network lifetime

Fig.8 Comparison of number of surviving nodes under four node samples (sample 1, sample 2, sample 3 and sample 4)

5 Conclusions

In this study, a wireless sensor network routing algorithm based on block clustering and springboard nodes was proposed. Firstly, it can effectively control the energy dissipation of the nodes and balance the number of member nodes of each cluster head by using block clustering to divide the nodes in the monitoring area into different block. In addition, the springboard nodes are used to forward the data of cluster heads far away from the BS to the BS, which balances the energy consumption of each cluster head and further reduces energy consumption. The simulation results show that the proposed routing algorithm can effectively balance the energy consumption of the cluster head, reduce the energy consumption of the network and extend the lifetime of the network.