A clustering routing protocol for wireless sensor networks based on energy and distance

0 Introduction

Wireless Sensor Network (WSN) is an intelligent special network composed of a large number of sensor nodes with specific functions that transmit information to each other through self-organized wireless communication to collaboratively complete specific functions. It integrates sensors, embedded computing, communications, distributed information processing, computer technology, and microelectronics manufacturing technology. It can monitor, sense, and collect various information in the monitored area in real time, and transmit the collected information to the end user after processing. It has broad application prospects in military, disaster sites, environmental monitoring, and medical rescue. Sensor networks are generally deployed in harsh environments or difficult-to-access areas. It is almost impossible to replace node batteries or replenish energy. Therefore, the design of energy-saving routing protocols is of great significance to wireless sensor networks. At present, the proposed WSN routing protocols mainly include flat routing protocols and hierarchical routing protocols. Among them, the hierarchical routing protocol based on cluster structure is the hot spot of current research at home and abroad.

1 Related Research

The primary goal of the design of WSN clustering routing protocol is to form a reasonable network structure through an efficient clustering algorithm, prevent the decline of network connectivity through active energy management, and extend the life cycle of the network. The most typical clustering routing protocol for wireless sensor networks is the LEACH protocol. People have also studied many improved clustering routing protocols based on the LEACH protocol. The EECS (Energy Efficient Clustering Scheme) protocol is one of the classic improved algorithms.

1.1LEACH protocolLEACH

is a representative of distributed clustering protocols. Each node generates a random number of 0 to 1. If this number is less than the threshold, the node broadcasts to the entire network that it is a cluster head. The threshold calculation formula is:



Where: p is the percentage of cluster heads to all nodes, that is, the initial probability of a node being elected as a cluster head. The actual cluster head probability fluctuates around p; r is the round currently being cycled; G is the set of nodes that have not been elected as cluster heads in the last 1/p rounds. It can be seen that the node that has been elected as a cluster head will not be able to become a cluster head in the next round, and the probability of other nodes being elected as cluster heads will increase as the probability of the node generating a random number less than T(n) increases. After the cluster head node that successfully competes broadcasts the message of being elected, other nodes decide which cluster to join based on the strength of the cluster head broadcast signal. Since cluster heads are randomly selected, the LEACH protocol cannot guarantee that cluster heads are evenly distributed in the network. In addition, the node selects which cluster to join based on the principle of minimum communication cost, but cannot guarantee cluster load balance.

1.2 EECS protocol

As mentioned above, in algorithms such as LEACH, nodes select which cluster to join based on the principle of minimum communication cost, which cannot guarantee cluster load balance, and does not consider the problem that cluster heads far away from the base station consume too much energy. In response to these problems, EECS proposes a new communication cost formula (2) to determine which cluster a node joins:



Where: cost(j, i) is the cost of node Pj joining cluster head i; d(Pj, CHi) is the distance from the node to the cluster head. In formula (3), the f sub-function ensures the minimization of the communication cost between the node and the cluster head; d(CHi, BS) is the distance from cluster head i to the base station, and the g sub-function in formula (3) ensures the minimization of the communication cost from cluster head i to the base station; the setting of the weight w is based on the specific application, and the trade-off between the energy consumption of the member nodes and the energy consumption of the cluster head is to maximize the network life cycle. Node Pj selects cluster head i with the smallest cost (j, i) to join, thus ensuring that each cluster head has a balanced load. Experimental results show that the network life cycle of the EECS protocol is more than 30% longer than that of the LEACH protocol.

2 Description of the problem

The essence of the EECS algorithm is to always select the node with the largest residual energy as the cluster head in the cluster head selection stage; in the clustering stage, the distance between the ordinary node and the cluster head, as well as the distance between the cluster head and the base station are jointly considered. Its innovation lies in: only a small number of nodes participate in the cluster head election; broadcast messages in a local range, and the election process is not iterated; the residual energy of the node is used as the election parameter; and a load balancing strategy between cluster heads is designed.

Problems with the EECS protocol:

(1) The EECS algorithm allows candidate nodes to broadcast the election message COMPETE_HEAD at the same time in the clustering stage, which is easy to cause cluster head distribution loopholes. As shown in Figure 1, node C is within the election radius of B; node B is within the election radius of A, and in terms of residual energy, A>B>C. In this case, C withdraws from the election after receiving the election message from B, and B withdraws from the election after receiving the election message from A, which will cause local cluster head distribution loopholes.

(2) The communication cost of the EECS algorithm in the clustering stage only considers the distance between ordinary nodes and cluster heads, and the distance between cluster heads and base stations, without considering the residual energy of cluster heads. This will cause the early death of some cluster head nodes with relatively less residual energy.

In response to the problems of the EECS protocol, the ADEECS (Advanced EECS) protocol was proposed. This algorithm uses the competitive delay method in the cluster head election stage and designs a new communication cost calculation formula in the clustering stage.

3 ADEECS routing protocol

In the scheme, it is assumed that the transmission power of the sending node is known, and the receiving node can calculate the approximate value of the distance between the two according to the strength of the received signal; the transmission power is controllable, that is, the node can adjust the transmission power according to its own needs. The same wireless transmission energy consumption model as in reference [5] is adopted. The ADEECS protocol is executed in rounds, and each round is divided into four stages: network deployment, cluster head election, clustering, and data transmission.

The specific implementation process is as follows:

Phase 1: Network deployment phase In the network deployment phase, the base station broadcasts a message HELLO_MSG to the network with a certain power. The sensor node calculates the approximate distance from itself to the base station based on the strength of the received signal, and selects the appropriate transmission power based on this distance when communicating with the base station. In the clustering phase, this information will also be used to balance the load of the cluster head.

Phase 2: Cluster head election phase A threshold T between 0 and 1 is pre-set globally to control the proportion of nodes participating in the cluster head election. Each node generates a random number between 0 and 1, denoted as u.

Where: T is the maximum agreed maximum delay time; Eresidual is the node residual energy; Eini is the node original energy.

Phase 3: Clustering phase The cluster head broadcasts the message HEAD_AD that it becomes the cluster head to all nodes in the network. The content is the identifier of the cluster head node and the distance between the node and the base station. After receiving this message, the ordinary node selects a cluster with the smallest communication cost (CH) to join and sends the message JOIN_REQ. The expression of communication cost is:

The parameters in formula (5) have the same meaning as those in formula (2) and formula (4). It can be seen from formula (5) that the communication cost comprehensively considers the distance between the node and the cluster head, the distance between the cluster head and the base station, and the residual energy of the cluster head. Therefore, the cluster member nodes select the cluster head with larger residual energy, closer distance to themselves, and smaller distance to the base station to form a cluster, so as to achieve the purpose of energy balance.

Phase 4: Data transmission phase The cluster head broadcasts TDMA communication time slot scheduling information TDMA_SCHEDULE to all member nodes. Member nodes send their detected data to the cluster head at a certain time according to the allocated TDMA time slot. The cluster head performs data fusion in the process of receiving data sent by cluster members, and directly transmits the fused data to the base station. This process adopts a single-hop communication method.

4 Simulation and analysis of ADEECS protocol

In the simulation, Matlab is used as the simulation platform, and the same energy consumption model as that in reference [3] is adopted. The simulation parameters are shown in Table 1.

In this paper, the performance of ADEECS is simulated and compared with that of EECS and LEACH protocols.

4.1 Simulation comparison of cluster head distribution

The number of LEACH cluster heads takes the optimal value. In the simulation, the number of LEACH cluster heads is 6; T=0.15, R=26, w=0.8 are taken. It can be seen from the cluster head distribution diagrams of the three protocols (Figures 2 to 4) that the LEACH protocol cluster heads are randomly distributed; the EECS protocol cluster heads are distributed relatively evenly, but there is a cluster head vulnerability problem; the ADEECS protocol cluster heads truly achieve uniform distribution. Therefore, the proposed method of delaying the sending of election messages has effectively solved the problems existing in the LEACH and EECS protocols in the cluster head election process.

4.2 Simulation comparison of network lifespan

The death time of the first node is defined as the network lifespan of the wireless sensor network, and the number of working rounds is used to represent the working time of the network. If there are too few remaining nodes, the existence of the entire network is meaningless. In order to better compare the simulation results, the simulation curve only selects the case where the number of remaining nodes is greater than 50. The simulation results are shown in Figure 5.

As can be seen from Figure 5, in the clustering stage, the ADEECS protocol comprehensively considers the remaining energy of the cluster head, the distance between the cluster head and the base station, and the distance between the cluster member nodes and the cluster head. This communication cost calculation method has greatly improved the network performance, effectively extended the network life cycle, and achieved the purpose of the protocol.

5 Conclusion

Through the research and analysis of typical clustering routing protocols, LEACH protocols and EECS protocols in wireless sensor networks, an improved clustering scheme ADEECS is proposed. The method of delaying the sending of contention messages and the new communication cost formula are used to solve the problems existing in the EECS protocol, achieve the uniform distribution of cluster heads, and effectively extend the network life. However, not only the parameter weight w and the communication radius R are not studied, which will be the focus of the author's next work. In addition, multi-hop-based ADEECS is also the next research direction.