Research on a Cluster Routing Algorithm for Wireless Sensor Networks

With the rapid development of microelectronics and wireless communication technology, the research on wireless sensor networks (WSN) has attracted more and more attention. A sensor network is composed of a large number of micro, cheap, and low-power sensor nodes deployed near the observation environment, forming a multi-hop wireless network system through wireless communication. Since wireless sensor networks are usually deployed in areas that are inaccessible or highly dangerous, and there are a large number of them, it is very difficult to replace the energy of nodes at any time. The relevant information collected by sensor nodes in the monitoring area usually carries disposable batteries and has limited energy. After a period of data collection, wireless sensor networks have serious energy constraints. Therefore, the primary design goal of sensor network protocols is to efficiently use the energy of sensor nodes and extend the survival time of the network. Organizing sensor nodes into clusters can effectively reduce energy consumption. Many energy-efficient routing protocols are designed based on cluster structures.

LEACH is a typical adaptive clustering protocol. Nodes in the network self-organize to form clusters in a random manner and send data to the cluster head in the allocated time slot. The cluster head fuses the received data and communicates directly with the base station after each frame. Nodes take turns to serve as cluster heads, which balances the energy consumption of the network. However, when the cluster head is elected, the energy level of the node is not considered. If the node has very low energy and still serves as the cluster head, it will accelerate its death. In addition, sending data directly to the base station will cause nodes far away from the base station to consume a lot of energy, resulting in the premature death of local nodes and the creation of monitoring blind spots.

Since the LEACH algorithm does not consider factors such as the residual energy of the node and the distance from the base station, many literatures have proposed corresponding improved algorithms. For example, EBAC is based on the LEACH protocol and periodically selects the node with the largest residual energy in the current round as the cluster head of the next round. LEACH-D is a multi-hop routing algorithm based on LEACH. Literature [6] proposed a method for constructing energy-balanced clusters. LEACH-L is a multi-hop routing algorithm that comprehensively considers the location and energy of the node.

Based on the LEACH protocol, this paper takes reducing the energy loss of long-distance communication between cluster heads and base stations as the primary goal. At the same time, the remaining energy of the nodes and the distance to the base station are comprehensively considered when selecting the second-layer cluster heads. The multi-hop path between cluster heads is improved to avoid using low-energy nodes. Matlab simulation shows that the algorithm can further balance the energy consumption of cluster head nodes and extend the life cycle of the network.

1 System Model

N sensor nodes are randomly and evenly distributed in a square area, periodically collecting surrounding environment information, and have the following properties:

(1) All sensor nodes will not move after deployment and have a unique ID;

(2) The base station is unique and located at a fixed location far away from the collection area;

(3) All nodes have similar capabilities (processing/communication) and are capable of data fusion;

(4) If the other party's transmission power is known, the node can calculate the approximate distance from the sender based on the strength of the received signal;

(5) The energy of the node cannot be replenished, but the transmission power of the node is controllable.

The same wireless communication model as that in reference [2] is used here: the free space model and the multipath fading model are used respectively according to the distance threshold d0. The energy consumed by the sender to send k bits of data to the receiver at a distance d is:

2 CAED Algorithm Description

Based on LEACH, a clustering algorithm based on energy and distance is proposed. The algorithm runs in rounds, and each round is divided into the establishment of two-layer cluster heads, data forwarding of nodes within the cluster, and transmission of stable data.

2.1 Establishment of Layer 2 Cluster Head

In the cluster establishment phase, the nodes that serve as cluster heads in the first round are randomly determined by the base station. The number of cluster heads is determined based on the location, size and network scale of the monitoring area. The IDs of the nodes selected as cluster heads are broadcasted in the network in sequence by the base station. The nodes in the network compare the received IDs with their own, and the ones that are the same are the cluster heads of this round. After all cluster heads are selected, the cluster head IDs are broadcasted to the entire network. In the last frame of each round of data transmission, the nodes in the cluster send information such as the remaining energy to their respective cluster heads. The cluster heads compare the remaining energy of the nodes in each cluster and select the node with the largest remaining energy as the cluster head for the next round, thus establishing the first layer of cluster heads.

The establishment and communication mode of the second-layer cluster head are quite different from those of LEACH. The first-layer cluster heads selected in each round become ordinary nodes of the second-layer cluster heads. In LEACH, these nodes communicate directly with the base station. It can be seen from formula (1) that the amplifier energy consumption is much greater than the circuit energy consumption, and the amplifier energy consumption is directly related to the communication distance d. Therefore, when generating the second-layer cluster head, factors such as the residual energy of the node and the distance between the node and the base station are fully considered. The threshold for generating the second-layer cluster head is calculated according to the following formula:

Where: Eresidual(i) is the residual energy of cluster head i; BSdistance(i) is the distance between cluster head i and the base station. In each round, when the first layer of cluster heads is generated and the cluster head energy is higher than a certain value Eth (if the node is lower than Eth, it is considered to be failed), each cluster head compares the Tch value and finds the second layer cluster head with the maximum Tch. Therefore, the second layer cluster head has both high energy and is closer to the base station, which can reduce the energy consumed when forwarding data and ensure that the node energy will not be exhausted quickly, which will affect data collection.

2.2 Data forwarding among nodes within a cluster

After the first-layer cluster head is selected in each round, the node selects the cluster to join based on the strength of the received broadcast signal. At this time, the free space model is used for intra-cluster communication. Different from the data communication of nodes in the first-layer cluster, since the nodes in the second-layer cluster are far away from the cluster head, some may far exceed the d0 value, and the free space model used for data communication may not be correct. In addition, the energy consumption of direct communication with the cluster head is large. Therefore, it is assumed that the nodes far away from the cluster head can communicate with the adjacent nodes with higher energy than themselves, and the data is forwarded through multiple channels to the cluster head, which meets the above assumptions as shown in formula (4):

Since the position of each cluster head in the cluster and the number of nodes in the cluster will change dynamically in each round, in order to analyze the best neighboring node of formula (4), four typical data forwarding modes under certain conditions are listed in Figure 1.

Figure 1(a) appears in the early stage of data collection. Due to sufficient node energy, nodes close to the base station adopt direct transmission, while nodes far from the base station select the next hop node for data forwarding according to formula (4); after multiple rounds of data collection, the nodes close to the base station rapidly reduce their forwarding energy due to excessive participation in data, and Figure 1(b) or Figure 1(c) appears according to formula (4); in the subsequent stage of data collection, due to the overall energy decline of nodes close to the base station, they respectively use a single hop method to communicate directly with the base station, and Figure 1(d) appears according to formula (4). During the entire data collection stage, nodes far from the base station communicate with adjacent nodes through multi-hop methods, indicating that the energy consumption of data forwarding through multi-hop is less than that of directly sending to the cluster head. At the same time, the energy of the node forwarding data is higher, which ensures that there is enough energy when forwarding data and balances the energy of the network.

2.3 Stable data transmission

In the stable data transmission stage, the communication mode between ordinary nodes and the first-layer cluster heads is the same as LEACH, but after data collection and fusion, the data packets are not sent directly to the base station, but are sent to the respective cluster heads of the first layer in a given time slot. The nodes of the second layer select the next hop node for data forwarding based on energy and distance until the cluster head of the second layer or directly communicates with the base station. After secondary data fusion, the cluster head nodes of the second layer send data to the base station.

3 Algorithm Analysis and Simulation Results

Matlab tool is used to simulate and compare LEACH, EBAC and CAED algorithms. The parameters are set as follows: Assume that the wireless sensor network consists of 300 identical nodes, randomly scattered in an area of ​​200 m×200 m, and the coordinates of the remote base station are (x==100 m, y=350 m). The initial energy of each node is E0=1 J, the loss of the sending and receiving circuits is ETX=ERX=50 nJ/b, the data fusion consumption is EDA=5 nJ/b, and εfs=10 pJ/(b·m-2) is dd0. Among them, d0 is a constant, the data packet length is 4 200 b, the broadcast packet length is 60 b, and the number of cluster heads kopt=5. When the node energy is lower than Eth=0.000 1 J, it is considered dead. Assume that the data fusion rate is 100%, and there is no data packet loss during the forwarding process. There is no bit error rate.

Figure 2 is a graph showing the relationship between the number of surviving nodes and the number of rounds. It can be seen that the LEACH curve is relatively steep throughout the life cycle, the number of surviving nodes in the network changes dramatically over time, and the energy of nodes in the network is unbalanced. The EBAC curve is smoother than the LEACH curve before 1,000 rounds. Since the residual energy is considered when electing the cluster head node, the performance is significantly better than that of the LEACH. However, the cluster head in EBAC communicates directly with the base station, which increases the energy loss of the cluster head node in remote communication. When running to a certain moment (about 1,094 rounds), a large number of nodes fail when the number of rounds is not much different. CAED takes the residual energy and distance into consideration, and uses multi-hop mode to forward data in the second-layer cluster. The curve of CAED is smoother than that of EBAC, which further extends the life cycle of the network.

Table 1 shows the number of rounds when the first node fails, the number of rounds when 30% of the nodes fail, and the number of node failures when the network runs 800 rounds. The values ​​in the table are the average values ​​obtained after running the corresponding algorithms multiple times. Here, the number of rounds when the first node dies is used to measure the network stability period, and 30% node failure is used to measure the network life cycle.

As shown in Table 1, compared with LEACH, the stability period of the CAED network is extended by more than 570%, and the network life cycle is extended by more than 458%. Compared with EBAC, the stability period of the CAED network is extended by more than 67%, and the network life cycle is extended by more than 20%. When the three algorithms are in 800 rounds, the number of node failures accounts for 81.7%, 11.7% and 3.7% of the total number of nodes respectively. The node energy consumption of the network is further balanced, avoiding the premature occurrence of "blind nodes".

Figure 3 shows the total residual energy of the network when the network runs the three algorithms. In the simulation experiment, a sampling record is made every 50 rounds. As can be seen from Figure 3, for the total residual energy of the network, CAED is significantly higher than LEACH and EBAC, indicating that CAED can save network energy well and extend the life cycle of the network.

4 Conclusion

A clustering multi-hop algorithm based on energy and distance is proposed. The residual energy of the node is considered when selecting the first-layer cluster head, and the second-layer cluster head fully considers the node energy and the distance to the base station, and improves the data forwarding method of the nodes in the cluster. Simulation results show that compared with the LEACH algorithm, this algorithm balances the energy consumption of the network and significantly extends the life cycle of the network.