Improvement of LEACH Algorithm Based on Inter-Cluster Ring Routing Strategy

Quanquan Xiao, Xing Hou

Guizhou University for Nationalities, Guiyang, China.

DOI: 10.4236/wjet.2020.84056                

Abstract

Wireless Sensor Network (Wireless Sensor Network, WSN) is a self-organizing network formed by a large number of wireless sensor nodes through radio communication [1]. The sensor nodes in the network cooperate with each other to monitor and collect the object information in the observation area, and the information is transmitted to the users who need this information after data fusion processing. It is often deployed in harsh environments, such as oceans, deep forests, and deserts. At the same time, the sensor nodes in the network are powered by batteries [2]. These external factors make it impossible to replace batteries manually. Therefore, energy is an important resource for wireless sensor networks [3]. In this paper, aiming at the problems of LEACH inter-cluster communication, from the perspective of energy saving, an improved strategy using inter-cluster ring routing is proposed. This strategy first abstracts all sensor nodes into a ring system model during the network topology formation stage. In the data transmission stage, a ring transmission strategy is adopted, and nodes on the ring are used to randomly and evenly undertake data transmission tasks, so the imbalance of energy consumption of sensor nodes can be effectively reduced. Simulation experiments show that this strategy can extend the network life cycle to a certain extent.

Keywords

Wireless Sensor Network, LEACH, Energy-Saving Routing, Hot Spot Effect

1. LEACH Algorithm and Existing Problems

The Low Energy Adaptive Clustering Hierarchy (LEACH) algorithm is a typical representative of the energy-saving routing algorithm. Compared with traditional planar routing algorithms such as Directed Diffusion and SPIN, it has greater advantages in energy saving and efficiency [4]. The LEACH algorithm uses the “round” [5] concept, and each round periodically performs the two operations of cluster establishment and data transmission. In the cluster establishment phase, all sensor nodes randomly generate cluster heads through autonomous cluster head elections, and the sensor nodes that become cluster heads randomly broadcast information to the surroundings [6]. The surrounding sensor nodes judge the cluster to join based on the strength of the received signal. In the data transmission stage, the sensor nodes in the monitoring area collect monitoring information [7]. After obtaining the time slot allocated by the cluster head, the information is sent to the cluster head, and the cluster head performs data fusion processing and transmits it to the base station [8]. After one round of the Leach algorithm, it enters the next round, and Leach algorithm re-selects cluster heads and divides clusters according to the same method described above, so as to achieve the effect of balancing the load of network nodes.

In the stable working phase, the cluster head mainly completes the transmission of the data collected by the member nodes in the cluster [9]. When the allocated time slot arrives, the sensor nodes in the cluster get an opportunity to transmit data to the cluster head and begin to transmit data. The time required for a sensor node to successfully send a data frame depends largely on the number of sensor nodes in the cluster.

In the data transmission stage, the cluster head close to the sink has a large amount of sending tasks, which not only needs to send the data collected by the nodes in the cluster, but also forward the data from other nodes. After the communication continues for a period of time, the nodes close to the BS will die the earliest, and the nodes close to the BS cannot forward the data sent by other nodes after death, thus forming a “hot spot effect” [10].

2. Inter-Cluster Ring Routing Strategy System Model

In the algorithm that adopts the inter-cluster ring routing strategy, the cluster head node is identified as a key node, and the ordinary sensor node is only responsible for data collection and is defined as a blind node. The system model consists of a batch of key node cluster heads and ordinary nodes covering the cluster head. The sensor consists of blind nodes, and the sink is at the center of the network. The system model is shown in Figure 1.

Figure 1. System model of ring routing strategy between clusters.

In the model, the black five-pointed star, square and triangle nodes represent the cluster head nodes on the first, second, and third layers, respectively, and the remaining circular nodes distributed around are general sensor nodes. For a node located in the nth ring, its ring number is counted as $\text{Layer}=n$. Hop number from node to sink is an important parameter of the model. Define the Hop value of the center sink as 0, and the Hop number of other nodes as:

$\text{Hop}\left(\text{Layer},i\right)=\left(\text{Layer},\Omega -i+\sigma \right)$ (1)

Among them, $\Omega$ represents the width of the ring and Layer is the ring number. As the network scale expands, the number of rings gradually increases. The adjustment factor i is used to adjust the hop count change caused by the change of the cluster head node, where $i\in \left[0,\Omega -1\right]$. The parameter $\sigma$ is used to identify whether it is a normal node or a cluster head node. The cluster heads and cluster head nodes of each adjacent ring are in a many-to-many relationship, and each cluster head maintains multiple neighbor node addresses and selects the optimal path to reach the sink. Figure 2 shows the sector model constructed by the sink node at the edge of the network. But Figure 1 can represent the generality of the network topology, so the model in Figure 1 is still used in the following discussion.

3. Inter-Cluster Ring Routing Strategy Topology Formation and Data Transmission Mode

3.1. Topology Formation Stage

The inter-cluster energy dichotomy algorithm is an improved algorithm of LEACH algorithm for inter-cluster communication, and other parts generally use LEACH algorithm. In the cluster head selection stage, each sensor node randomly generates a random number between [0, 1]. If the random number is less than the set threshold $T_n\left(t\right)$, it becomes a cluster head, otherwise it becomes a non-cluster head node. In order to build the ring system model, the cluster head broadcasts the information frame to the entire network. The frame format is shown in Figure 3.

Among them, the flag is used to distinguish other information in the network; $\Omega$ represents the width of the ring; the number of hops CNT records the number of hops that the information has reached the sink in the network, ID

Figure 2. Sink in the network edge system model.

Figure 3. Networking information frame structure.

represents the address of the node, and Eava is the remaining energy of the node. In the initialization phase, after the node receives the networking information, the first step: the node i checks the CNT item in the frame. If CNT > Local CNT, it means that the information comes from the outer node, and the node i directly discards the frame. If, CNT = Local CNT, it means it is from the same layer, and the node directly discards the frame. If CNT = Local CNT, then update the local CNT to CNT. Step 2: After the node i updates the local CNT, it obtains the number of hops to sink, takes out the Eava value and ID address in the networking information frame, writes this information into the routing table of the node, and then the node forwards the information.

Finally, the cluster head nodes in the network can form a system topology similar to that shown in Figure 1. Each cluster head node can confirm the ring number Layer in the network and the information of other nodes in the ring.

3.2. Data Transmission Stage

Assuming that the outermost ring is the nth ring, the inward ring is $n-1$ ring, $n-2$ ring, …, ring 1, and the sink is located on ring 0. The cluster head node in the network is counted as $C{H}_i$, and the number of hops between the cluster head $C{H}_i$ and sink is counted as $\text{CNT}\left(C{H}_i,\text{Sink}\right)$, The data transmission process is as follows:

1) The cluster head broadcasts its own number of hops $\text{CNT}\left(C{H}_i,\text{Sink}\right)$ and energy E to the surroundings with a radius R, and obtains ( $I{D}_i$, CNT) through learning information exchange to form global information $SC{H}_i$, which is expressed as $\left\{C{H}_{n1},C{H}_n{}_2,\cdots ,C{H}_{nn}\right\}$, $\left\{C{H}_{\left(n-1\right),1},C{H}_{\left(n-1\right),2},\cdots ,C{H}_{\left(n-1\right),n}\right\}$, $\cdots$, $\left\{C{H}_{11},C{H}_1{}_2,\cdots ,C{H}_{1n}\right\}$, where $C{H}_{nn}$ is the node with sequence number n on the nth ring.

When n is an even number, the data on the $n,n-1,\cdots ,n/2+1$ rings are transferred to the $n/2,n/2-1,\cdots ,1$ rings respectively, and then directly to the sink. When n is an odd number, the data on the $n,n-1,L,\left(n+3\right)/2$ ring is transferred to the $\left(n+1\right)/2,\left(n-1\right)/2,L,2$ respectively, and then directly to the sink, and the data on the $\left(n+1\right)/2$ ring is transferred to the sink through the nodes on the first ring.

2) Since there are multiple cluster heads $C{H}_{nn}$ in each ring, in the process of transmitting information to a ring, the node with the largest energy is selected as the next hop node. If the remaining energy of multiple cluster heads is the same, the nearest cluster head is selected as the next hop routing node.

The algorithm flow of the inter-cluster ring routing strategy is as follows:

1. for each cluster CHi

2. broadcast hello in R

3. find Global information

4. begin

if n is even number then

if i > n/2 then

set its transmit radius = rk/2

else set transmit radius = ir

5. find max Energy in SCHi

6. if Ei in SCHi is equal

7. CHi is the shortest distance

else

if i > (k + 1)/2 then

set transmit radius = r(k − 1)/2

else set transmit radius = ir

end

8. find max Energy in SCHi

if Ei in SCHi is equal

CHi is the shortest distance

end

Figure 4 shows the energy dichotomy model where n is an even number of 8 nodes.

The data is transmitted from the 8th ring to the $8÷2=4$ ring, the 4th ring is transmitted to the sink, the data on the 7th ring is transmitted to the $8/2-1=3$ ring first, and the 3rd ring is transmitted to the sink; the data on the 6th ring is transmitted to the $8/2-2=2$ ring, and the second ring Transfer to the sink; and so on, the data on the fifth ring is transferred to the $8/2-3=1$ ring, and the first ring is transferred to the sink. Figure 5 shows the ring routing strategy model between clusters of 7 nodes where n is an odd number.

Data is transmitted from ring 7 to ring $\left(7+1\right)/2=4$, from ring 4 directly to ring 1, and then to sink; ring 6 is transmitted to ring $\left(7+1\right)/2-1=3$, ring 3 is transmitted to sink; on ring 6 The data is transmitted to the $\left(7+1\right)/2-2=2$ ring, the second ring is transmitted to the sink; and so on, the data on the fifth ring is transmitted to the $\left(7+1\right)/2-3=1$ ring, and the first ring is transmitted to the sink.

Aiming at the problem of “hot zone effect” produced by LEACH algorithm. In the inter-cluster ring routing strategy algorithm, taking 4 ordinary nodes and a

Figure 4. The 8-node ring routing strategy model between clusters.

Figure 5. 7-node ring routing strategy model between clusters.

sink node as an example, the data is transmitted from the fourth ring to the 4/2 = 2 ring, the second ring node is transmitted to the sink; the third ring data is from 4/2 − 1 = 1 ring, the node on the first ring transmits to the sink. This ensures that the set of sensor nodes that are close to the sink share the relay task. The nodes that are far away only need to transmit data to n/2, so they consume less energy than using single-hop and multi-hop communications. It is compatible with the advantages of single-hop and multi-hop between clusters, and is superior to single-hop communication and multi-hop communication in terms of extending the network life cycle.

4. Experiments Verify that the Inter-Cluster Ring Routing Strategy Algorithm Is Superior to the Data Transmission Mode of Single-Hop Communication or Multi-Hop Communication in Energy Saving

4.1. Establishment of Simulation Environment

In order to avoid interference from other factors, it is much clearer to verify that the inter-cluster ring routing strategy is more effective than single-hop communication and multi-hop communication between clusters. The experiment only observes the communication mode between the cluster head and the cluster head, and the intra-cluster node communication is ignored. The network simulation topology is shown in Figure 6.

Among them, n0 is set as the sink node, the initial energy is large and energy consumption is not considered. n1, n2, n3 and n4 are the cluster head nodes. Set the energy model value to Energy Model, the initial energy value of the sensor is 2J; the energy consumption per unit time for sending and receiving data is 2.0mw; the energy consumption per unit time during sleep is 0.001mw, between clusters. The routing mode is static routing, and the value is NOAH.

The source node n1, n2, n3, and n4 set up an Agent to send messages, and the destination n0 set a SinkAgent to receive messages. Then, the source node uses the CBR traffic generator to generate a service flow at a fixed rate and send a 500 Byte message to the sink node. At the same time, the data packet size transmitted by the network layer is set to 1500 Byte. The fixed transmission rate CBR is built on UDP. The transmission rate of CBR is 1 Mps, and the size of each packet is 500 Byte. CBR starts transmission in 1 s and ends in 50 s.

4.2. Comparative Analysis of Simulation Results

1) NAM analysis and comparison

Figure 6. Network simulation topology.

In Figure 7 NAM animation scene, all sensor nodes have the same initial energy. When the remaining energy of the sensor node is sufficient, the color of the node is displayed in green; when the energy of the sensor node enters the warning zone, the color of the node changes to orange; when the remaining energy of the sensor node is 0, the color of the node is displayed in red. When node n1, n2, n3, n4 communicate with node n0 for a period of time, as shown in Figure 8, the node on the fourth ring that is farthest from the sink at about 12.911467 s will die first and other nodes still have a lot of energy. It can be seen that when single-hop communication between clusters is used, the farther away the sensor node is from the sink, the greater the energy consumption, the farthest node from the sink is likely to die first, and the energy of the entire system is extremely uneven. Even if the nodes on the first ring have greater energy, the death of the nodes on the fourth ring leads to the end of the network life cycle, and the running time of the system is rapidly reduced.

In Figure 8 inter-cluster multi-hop communication, the situation is opposite to inter-cluster single-hop communication. The node closest to the sink dies first. The node close to the sink not only consumes energy to send data, but also forwards data from other rings. Therefore, the n1 node first died and turned red at 16.915288 s. In this way, even if the node far away from the sink has a lot of energy, the information cannot be transmitted to the sink due to the failure of the next hop node, forming a hot spot effect. Therefore, the life cycle of a multi-hop communication network is closely related to the energy consumption of the first ring nodes. The nodes far away from the sink consume less energy, and the nodes near the sink consume more energy.

Figure 7. When the first node of single-hop communication between clusters dies.

Figure 8. When the first node of multi-hop communication between clusters dies.

In the ring routing strategy communication between clusters in Figure 9, the communication mode is carried out in an ideal state, and the data on the $n,n-1,\cdots ,n/2+1$ -th ring is transferred to the $n/2,n/2-1,\cdots ,1$ ring respectively, and then the information is directly transferred to the sink node. The energy consumption of the nodes on the first, second, and third rings closest to the sink is relatively average. At 22.284872 s, node 1 enters a low energy consumption state, and node 2 died. From the animation view, it can be seen that several sensor nodes close to the sink in the inter-cluster ring routing strategy communication share the energy consumed by transmitting the information transmitted by other nodes. From the comparison of the network life cycle, it can be clearly seen that the communication life cycle time of the inter-cluster ring routing strategy is better than that of multi-hop communication and single-hop communication, which is consistent with the expected results.

2) Trace file data analysis

A screenshot of the data part of the Trace file is shown in Figure 10.

Each record of Wireless Trace has 21 columns. In the first column, s means packet sending data; r means packet receiving event; d means packet discarding event; f means packet forwarding event. The second column indicates the time when the event was generated, the third column indicates the ID of the processing event node, the fourth column indicates different types of Trace, the fifth and sixth columns are separators, the seventh column is the ID number of the transmission packet, and the eighth The column indicates the type of the packet, the ninth column indicates the size of the packet transmitted at the transport layer, the 10th column is the expected value of the sending node to send the packet on the wireless channel, the 11th column is the MAC address of the receiving node, and the 12th column is the sending node The 13th column is

Figure 9. Inter-cluster ring routing strategy when the first node dies.

Figure 10. Trace file.

the packet type encapsulated by the MAC layer, the 14th column is the energy value, the 15 - 17 column is the separator, the 18th column is the source IP address of the sending packet, and the 19th column is the destination IP of the receiving packet Address, the 20th column is the TTL value of the packet, and the 21st column is the number of hops from the source node to the destination node. The Trace file records all the information of each data packet in the network at each time. The performance of single-hop, multi-hop and inter-cluster ring routing between clusters is judged based on the data in the out.tr file. It can be seen from this document that in this network scenario, the number of nodes surviving in the network during the same period of time is obviously better than single-hop and multi-hop communication between clusters.

Acknowledgements

This paper analyzes the LEACH routing algorithm designed to save energy. The algorithm transmits data to the sink node through the cluster head hop by hop. Sensors near the sink node will take on a large amount of tasks, resulting in excessive energy consumption and death of neighboring nodes. By comparing the advantages and disadvantages of single-hop and multi-hop transmission between clusters, a strategy of inter-cluster ring routing is proposed. Simulation experiments are carried out using NS2, which verifies that the strategy can better reduce the imbalance in energy consumption of sensor nodes, thereby achieving prolongation.

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Cui, D. (2009) The Composition and Application of WSN. Solutions, 5, 41-43.
[2]	Cui, X.Y. (2009) The Origin of WSN and its Research and Development Abroad. Solutions, , 5, 45-48.
[3]	Chen, D., Zheng, Z.W. and Li, J.J. (2009) Overview of Wireless Sensor Networks. Computer Measurement and Control, 8, 46-48.
[4]	Wit, E. and McClure, J. (2004) Statistics for Microarrays: Design, Analysis, and Inference. 5th Edition, John Wiley & Sons Ltd., Chichester.
[5]	Kulkarni, S.S. and Arumugam, M. (2004) TDMA Service for Sensor Networks. Proceedings of 24th International Conference on Distributed Computing Systems Workshops (ICDCSW), Tokyo, 23-24 March 2004, 604-609. https://doi.org/10.1109/ICDCSW.2004.1284094
[6]	Zhou, Y.Y. and Yu, L. (2008) Research Status of WSN Energy-Saving Design. Network Communication and Security, 6, 13-16.
[7]	Zou, D., Chen, S.Y., Han, S., Meng, W.X., An, D., Li, J.Q. and Zhao, W.L. (2020) Design of a Practical WSN Based Fingerprint Localization System. Mobile Networks & Applications, 25, 806-818. https://doi.org/10.1007/s11036-019-01298-4
[8]	Moorthi and Thiagarajan, R. (2020) Energy Consumption and Network Connectivity Based on Novel-LEACH-POS Protocol Networks. Computer Communications, 149, 90-98. https://doi.org/10.1016/j.comcom.2019.10.006
[9]	Jayarajan, P., Kanagachidambaresan, G.R., Sundararajan, T.V.P., Sakthipandi, K., Maheswar, R. and Karthikeyan, A. (2020) An Energy-Aware Buffer Management (EABM) Routing Protocol for WSN. The Journal of Supercomputing, 76, 453-4555. https://doi.org/10.1007/s11227-018-2582-4
[10]	Anitha, G. and Vijayakumari, V. (2019) Novel Fuzzy Based Approach for Maximizing Network Lifetime through Optimal Cluster-Head and Relay Node Selection in Wireless Sensor Network. Journal of Intelligent & Fuzzy Systems, 37, 1019-1031. https://doi.org/10.3233/JIFS-181923