Abstract: Based on the research of low-energy adaptive clustering routing algorithms and routing protocols such as LEACH for wireless sensor networks, a dynamic topology energy-efficient clustering algorithm for wireless sensor networks is proposed. Its main contents include: 1. Employing a low-complexity cluster head selection algorithm that incorporates an energy factor. 2. Supporting a dynamic topology network with partial node movement. 3. Implementing multi-hop information routing for data transmission. Theoretical and simulation results demonstrate that this algorithm improves network lifetime compared to the LEACH algorithm.
1 Introduction
Wireless Sensor Networks (WSNs), as a next-generation information acquisition technology, have attracted worldwide attention and are increasingly becoming a research hotspot for academic institutions both domestically and internationally. A WSN is typically a self-organizing network system formed by a large number of sensor nodes communicating via radio frequency. It provides useful information to managers by sensing, acquiring, and processing information about monitored objects, and can be widely applied in smart homes, healthcare, industrial control, agriculture, military early warning, and flood control and disaster relief. However, WSNs differ significantly from Mobile Ad Hoc Networks (MANETs). Their communication methods, purposes, and network topologies are very different, especially in terms of power sources. WSNs are battery-powered, and routing algorithms have a significant impact on the lifespan of sensor networks. Therefore, routing protocols for Mobile Ad Hoc Networks are not entirely suitable for WSNs, and we need to study communication protocols specifically designed for wireless sensor networks.
2. Dynamic Topology Energy Efficient Clustering Algorithm
To address various issues in hierarchical routing protocols, this paper proposes a Dynamic Topology Energy-Efficient Clustering (DTEE) algorithm suitable for WSNs. This algorithm introduces a low-complexity cluster head selection mechanism based on energy factors, and through protocol design, it supports dynamic sensor networks with partial node departures or new node additions. For inter-cluster data transmission, a multi-hop algorithm ensures data is transmitted to the sink node via the optimal path, resulting in minimal system energy consumption and maximized network lifetime.
3.1 Network Model
This paper assumes that the sensor nodes are randomly distributed within a rectangular monitoring area, and that the sensor network has the following properties:
1) All sensor nodes in the network are isomorphic, have the same initial energy, and have finite energy;
2) The transmission power of the sensor node can be discretely adjusted, and its transmission power can be adjusted according to the transmission distance.
3) The aggregation node has strong computing power and large storage capacity, and its energy is unlimited. Its wireless signal can cover the entire sensor network.
4) After the sensor network is deployed, some nodes may move over time;
5) The sensor nodes have data fusion capabilities.
6) Data collected from adjacent nodes in terms of location are highly correlated.
3.2 Energy Model
In wireless transmission, the signal strength decreases exponentially with the increase of transmission distance. Reference [3] proposes two channel models: the free space model and the multi-path fading model. When the distance d between the transmitter and the receiver is less than the threshold, the free space model is used, and the signal power decreases by d; otherwise, the multi-path fading model is used, and the signal power decreases by d .
3.3 Clustering Strategy
In the LEACH algorithm, the execution process is periodic, with each round including a cluster establishment phase and a stable data transmission phase. During cluster establishment, a node is elected as the cluster head. The cluster head broadcasts a message to surrounding nodes, and other nodes select the cluster to join based on the strength of the received broadcast message, informing the corresponding cluster head. The DTEE algorithm proposed in this paper also operates periodically in rounds, but it introduces an energy factor in cluster head election. Furthermore, the algorithm process differs between the first and subsequent rounds. From the second round onwards, no calculation formula is required during the clustering phase. Compared to LEACH and some improved algorithms, which require complex formula calculations, this algorithm reduces complexity and minimizes the energy cost of cluster head election. The non-uniform clustering method used in the clustering process further promotes a more balanced network energy distribution.
Since this paper employs intra-cluster single-hop and inter-cluster multi-hop data transmission, cluster head nodes farther from the sink node have less data forwarding and consume energy more slowly. Conversely, cluster head nodes closer to the sink node bear more data forwarding traffic and consume more energy, making them more prone to energy exhaustion and failure. Therefore, this paper abandons the uniform clustering method used in traditional algorithms and instead adopts a non-uniform clustering strategy. Clusters closer to the sink node are smaller, resulting in lower intra-cluster routing and data fusion overhead. Because these clusters bear higher inter-cluster data forwarding overhead, overall, energy consumption is relatively evenly distributed across cluster head nodes, maximizing network lifetime.
The implementation process of non-uniform clustering is as follows: First, the Sink node broadcasts a NOTICE message to the network area. All nodes in the network determine their distance d(i) from the Sink node based on the energy intensity information received from this message. The number of network layers n is determined according to the monitoring area, the number of sensor nodes, and the energy free space model. Then, this paper adopts the uniform layering method in reference [14], where the layer number i of each node is d(i)*n/R, and R is the radius of the monitoring area. Because the cluster size near the Sink node is small and there are few nodes in the cluster, the probability of nodes in different layers becoming cluster heads is different. The optimal probability of each node becoming a cluster head is pi=p/(i*i). Where p is the probability of the first layer node becoming a cluster head. The action of dividing the sensing area only occurs at the beginning of the first cycle. The subsequent cycle does not need to divide the sensing area again.
3.4 Cluster Head Selection
Then the first round of election begins. Each node generates a random number r(n) and compares it with T(n). If r(n) is less than T(n), the node is elected as the cluster head.
G is the set of nodes that did not become cluster heads in this round of the cycle.
Once a node becomes a cluster head, it broadcasts a cluster head join message with an appropriate radius (RC). Surrounding nodes determine which cluster to join based on received signal strength and send a join request message. After receiving the join request message from the relevant node, the cluster head establishes a TDMA scheduling table and broadcasts it. Upon receiving this message, nodes within the cluster activate their radio modules to begin data transmission in their assigned time slots and deactivate communication in other time slots to conserve energy. When a node sends a data packet to the cluster head, it includes information about its current remaining energy level for subsequent algorithm use.
In the second and subsequent rounds of cluster head generation, the old cluster head first compares the energy information of each node in the received node messages with its own remaining energy, selecting the node with the largest remaining energy as the new cluster head. Then, the old cluster head sends a `new_CH` message with a radius RC, including the message type and the ID of the new cluster head. When the designated new cluster head receives this message and finds a match in the ID, it broadcasts a cluster head join message. The remaining nodes then decide which cluster head to join based on the received signal strength, and the process is the same as in the first round. However, in practical applications, network nodes may be accidentally moved or fail, meaning the designated new cluster head may no longer exist. Consequently, nodes within that cluster will cease operation due to the lack of a cluster head join message, creating a dead zone in the network. To address this, this paper sets a time threshold at which an old cluster head node, if not receiving a cluster head join message from the designated new node within a certain time threshold, confirms that the designated new node has been moved. It then designates the node with the second largest remaining energy as the new node and sends a new `new_CH` message. This new algorithm supports networks with dynamic topologies where some nodes move or new nodes are added.
Meanwhile, this paper designs that in any round of the loop, all nodes start a timer when they receive a cluster head join message or a new_CH message. If no new cluster head join message or new_CH message is received within the maximum time limit Tmax, a new cluster head selection process is started from the first round. Compared with most algorithms that only support static networks, the algorithm in this paper supports sensor networks with small-scale geographical changes.
3.5 Data Transmission
In sensor networks, intra-cluster data transmission is single-hop, occurring between the cluster head and each member node. However, for data transmission from the cluster head to the sink node, the LEACH algorithm and some improved algorithms use single-hop transmission from the cluster head to the sink node. This method causes the cluster head to use a multipath fading communication model (reference [3]), resulting in high energy consumption. This paper adopts a multi-hop transmission method based on the distance factor. Due to the use of multi-hop communication, the energy consumption follows a free-space model, and the message undergoes multiple data fusions during transmission, reducing the amount of data in each level of data forwarding and thus reducing communication energy consumption. All nodes in the network store their distance values from the sink node, determined based on the signal received from the sink node. This distance value is determined before the first round of clustering and is called the distance factor. After the intra-cluster data fusion of each cluster is completed, multi-hop data transmission from each cluster to the sink begins.
First, the cluster head sending data sends a message within a defined radius RD. This message includes a distance factor for that cluster head. Upon receiving the message, neighboring cluster heads compare this distance factor with their own. If their distance factor is smaller than the one in the message, and their remaining energy is not lower than the minimum energy threshold Emin required for inter-cluster transmission, they decide to forward the data. They replace the distance factor in the message with their own distance factor and continue forwarding with the radius RD. Subsequent transmission processes are similar. Because the cluster head forwarding the message has a smaller distance factor, it is closer to the sink node. This allows the message to travel to the sink node via a multi-hop optimal path, minimizing transmission energy overhead.
3. Simulation Study
NS2 (Network Simulator 2) is a well-known discrete event simulation tool for network research. It includes a large number of network protocols, schedulers, and tools for simulating TCP protocols, routing algorithms, and multicast protocols over wired and wireless, local connections, or satellite connections. The core of NS is a discrete event simulation engine. NS has a "Scheduler" class responsible for recording the current time, scheduling events in the network event queue, and providing functions to generate new events, specifying the time of event occurrence. During the simulation, relevant algorithms are executed, and the specific details of network operation are written to files, including data packet transmission and node energy status. These files are very useful for comparing algorithms. This paper uses the following scenario setup scheme for simulation scenario settings:
(1) The simulation area size is (100*100).
(2) All nodes have the same initial energy.
(3) Sensor nodes are randomly distributed within the area (100*100).
At the start of the simulation, the distribution of sensor nodes within the network is shown in Figure 1.
After the simulation was completed, the relevant files generated by the LEACH and DTEE algorithms were obtained. The key data in the relevant files generated by the algorithms were extracted using the awk program, and then the gnuplot tool was used to display these data on the graphs, resulting in a curve comparing the two algorithms, as shown in Figure 2.
As shown in the figure, during the simulation, the energy of a node gradually decreases over time until it runs out of energy and dies. Therefore, the number of nodes still having energy in the sensing area varies at different time points. The figure compares the number of surviving nodes for the two algorithms at different time points. First, the first node in the LEACH algorithm dies at 120 seconds, while the first node in DTEE dies around 130 seconds. The node survival count graph shows that around 300 seconds, the number of surviving nodes in the LEACH algorithm is 0, while the DTEE algorithm still has 8 nodes with energy remaining. All nodes in the DTEE algorithm die around 320 seconds. Therefore, the node lifetime in the DTEE algorithm is about 6% longer than that in LEACH. This demonstrates that the DTEE algorithm, by employing a multi-hop routing method, extends the network lifetime to a certain extent.
This paper reduces network communication energy consumption by employing a low-complexity cluster head selection algorithm that incorporates an energy factor, and routes information via a multi-hop approach for data transmission. Simulation results show that the improved DTEE protocol better balances network load, saves energy consumption, and has higher energy efficiency, thus optimizing the routing protocol of the clustering algorithm.
After the simulation was completed , the relevant files generated by the LEACH and DTEE algorithms were obtained . The key data in the relevant files generated by the algorithms were extracted using the awk program, and then the gnuplot tool was used to display these data on the graphs, resulting in a curve comparing the two algorithms, as shown in Figure 2 .
As shown in the figure, during the simulation, the energy of a node gradually decreases over time until it runs out of energy and dies. Therefore, the number of nodes still having energy in the sensing area varies at different time points. The figure compares the number of nodes still alive at different time points for the two algorithms. First, the first node of the LEACH algorithm dies at 120 seconds, while the first node of DTEE dies at around 130 seconds. The node survival count graph shows that around 300 seconds, the number of surviving nodes in the LEACH algorithm is 0 , while the DTEE algorithm still has 8 nodes with energy remaining. All nodes in the DTEE algorithm die around 320 seconds. Therefore, the node lifetime in the DTEE algorithm is about 6% longer than that in LEACH . It can be seen that the DTEE algorithm, due to its multi-hop routing method, extends the network lifetime to a certain extent.
This paper reduces network communication energy consumption by employing a low-complexity cluster head selection algorithm that incorporates an energy factor, and routes information via a multi-hop approach for data transmission. Simulation results show that the improved DTEE protocol better balances network load, saves energy consumption, and has higher energy efficiency, thus optimizing the routing protocol of the clustering algorithm.
