# A Competition-Based Unequal Clustering Multihop Approach for Wireless Sensor Networks

Authors: Jing Liu; Shoubao Su; Yuhua Lu; Jun Dong
Journal: Security and Communication Networks
 (2021)

---

## Abstract

The energy efficiency and stability of wireless sensor networks (WSNs) have always been a hot issue in the research. Clustering is a typical architecture for WSNs, and cluster heads (CHs) play a vital role. Unreasonable CH selection causes a lot of energy consumption. In this paper, we propose a competition-based unequal clustering multihop approach (CUCMA). CHs are selected by competition. First, the cluster radius (CR) of a node is calculated according to the distance to base station (BS). Then, CR is resized based on the number of around nodes. Only the nodes with high residual energy and appropriate distances to the selected CHs maybe become CHs, which are usually closer to the surrounding nodes. CUCMA and four related approaches are simulated in different scenarios. The results are analyzed, and it is proved that CUCMA balances the energy consumption of the CHs and reduces the energy consumption of the whole networks, thus leading to prolong the lifetime of WSNs.


---

## Body

## 1. Introduction

A WSN is composed of a large number of sensor nodes with sensing, computing, and communication capabilities. WSNs play an important role in environmental monitoring, smart cities, fine agriculture, and many other fields [1]. Sensor nodes are usually powered by batteries with limited energy. If the battery of a node has run down, the node becomes useless and we call it as a dead node. Reducing energy consumption to delay node death is one of the challenges of WSNs, and many approaches are designed to get the best performance with limited energy [2]. The relevant energy-efficient strategies are classified into five categories, the Energy-Efficient Media Access Control (EEMAC) protocol, the Mobile Node Assistance Scheme (MNAS), the Energy-Efficient Clustering Scheme (EECS), the Energy-Efficient Routing Scheme (EERS), and the Compress Sensing-Based Scheme (CSS), respectively [3]. We propose an effective method to reduce network energy consumption for EECS strategy.Layered architectures can cut down the energy consumption of a network, especially a large WSN [4, 5]. Clustering is a typical layered architecture. Nodes are divided into different clusters, and each cluster has a node called cluster head (CH) that collects data from other nodes in the cluster. CHs aggregate data before sending them to BS because the data from nodes in a same cluster are similar [2]. Clustering approaches reduce the load on the network by aggregating data, which results in a longer network lifetime [6, 7]. The selection of CH is particularly important. A large number of literatures provide the scheme of CH selection. Some choose the CH based on the back propagation technology of artificial neural network to improve the network energy efficiency and robustness [8]. Others choose Energy Efficient Quad Clustering to improve the performance of wireless sensor network in terms of network lifetime [9]. However, these methods are complex, and the selection time of CH is long.This paper proposes a novel CH selection approach for WSNs. The approach selects CHs by an adaptive competition scheme. A node decides whether it has the chance to be a CH according to the residual energy, the distance to BS, the distances to selected CHs, and the number of around nodes, and then, among the nodes with opportunities, CH is the one close to the surrounding nodes. Each sensor node makes the selection by itself, so the approach is distributed.The main contributions of this paper are as follows:(1)
We create the network and energy consumption model to adapt to the application of the CUCMA algorithm(2)
We propose a novel balanced-load clustering heads selection algorithm with smaller energy consumption in the network lifetime(3)
In different scenarios, we compare the energy consumption and network lifetime of the new algorithm with the previous algorithms by simulationsThe rest of the paper is arranged as follows. Section2 gives a brief overview of related work in this field. Section 3 gives the network models and calculating equations of energy consumption. Section 4 describes the approach we proposed. Simulations are carried on in Section 5, and the results are discussed. In Section 6, we summarize the paper and give the conclusions.


## 2. Related Works

LEACH is an early clustering approach for WSNs [10]. LEACH selects some nodes as CHs in all nodes. A node selects the nearest CH to join its cluster. A CH receives the data from the nodes in its cluster, then aggregates, and sends data to BS. When selecting CHs, each node produces a random number between 0 and 1. If the number is less than T (i), the node becomes a CH. T (i) is calculated as follows:(1)Ti=p1−p×roumod1/p,ifi∈F,0,else,where i is a node, p is the desired percentage of CHs, rou is CH selection round, and F is the set of nodes which are not selected as CH yet in recent rou rounds [11]. LEACH balances load among all nodes by reselecting CHs in each round and prolongs the lifetimes of WSNs.LEACH has two drawbacks. One is the random on selecting CHs. The distribution of CHs is random, which makes clustering unreliable [12]. Another is the great energy consumption for large WSNs. A CH sends data to BS directly without forwarding by other CHs; thus, the energy consumption is great if a CH is far from BS, which makes LEACH not suitable for large networks [13].LEACH-MAC reduces the random in CHs selection by ensuring that the CHs number is equal to optimum value and CHs are selected only in the nodes with high residual energy [14]. LEACH-MAC improves the overall network lifetime but it is not suitable for larger networks yet and the distribution of CHs is still random.Reference [15] limits the distance between two CHs to evenly distribute the CHs. However, all clusters have the same size in this approach, so it is not applicable for large WSNs.Some references propose double hierarchical CH election approaches. Reference [16] proposes some new hierarchical clustering topology architectures. These approaches divide all nodes into some clusters and then divide a cluster into some subclusters. CHs are selected randomly, and sub-CHs are selected in the nodes with high residual energy. DL-LEACH [17] chooses level one CHs to be responsible for receiving and aggregating data. Level two CHs are responsible for forwarding data to BS.If the size of network is relatively large, the energy consumption of a CH sending data directly to BS is high due to the far distance, so multihop communication is suitable for large WSNs. In multihop WSNs, a CH sends data to another CH which is closer to BS; data may be relayed several times by CHs before sent to BS [18]. Obviously, the CHs which are close to BS forward heavy communication load and consume more energy for intercluster communication. Approaches have been proposed to solve the question, such as unequal clustering. A cluster size decreases as its distance to BS decreases. As a result, clusters closer to BS are expected to have smaller cluster sizes, so the intracluster energy consumption of a CH closer to the BS is low [19].Reference [20] proposed an unequal clustering multihop approach. A node calculates its competition radius based on the distance to BS. The competition radius decreases as the distance to BS decreases. During CHs selection, once a node has become a CH, all other nodes within the circle of the competition radius quit the selection for CHs.The number of around nodes and the average distance to these nodes affect energy consumption of a CH [21]. The bottleneck of node energy consumption is attributed to the cluster with high density [22]. Reference [23] and Reference [24] select CHs in accordance with total distance which is the sum of distances from a CH to all the nodes within the cluster. A node with high residual energy and low total distance is more likely to become a CH.Reference [25] uses particle swarm optimization technique to improve clustering energy efficiency of wireless sensor networks. Clustering coefficient, residual energy, and distance from member nodes are taken as optimization parameters to select CHs.Reference [26] proposed a clustering approach called ACCA. CHs selection is performed based on competition. Nodes which are with high residual energy and closer to the center of the density of the nodes are selected to be CH candidates. Then, the candidates with suitable distances to other candidates are selected as the CHs.EAUCA divides the competition radius of unequal clusters based on the residual energy of nodes and the distance to the BS, then selects the CHs according to the degree of competition radius, and separates the functions of CHs and relay nodes, so as to reduce the energy consumption of CHs [27].CEECR selects an optimal CH according to the node distance property, node mobility, and the node energy property. By using the centralized cluster formation algorithm, energy consumption is minimized and packet transmission rate is maximized [28].The ideas and results of these relate approaches reflect that unequal clustering multihop approach is suitable for large WSNs. These approaches prolong WSNs lifetime to some degree but have their own flaws. Residual energy, distance to BS, distances to selected CHs, number of around nodes, and distances to around nodes are the major determinants of CHs selection and clustering. These approaches usually select CHs according to some of the determinants, but it is hard to take all the determinants into consideration and the weight of each determinant is difficult to calculate. Another common flaw is that these approaches avoid CHs become too close from each other, so that the distance between two CHs may be too large.


## 3. Network and Energy Consumption Model

We assume that a WSN covers a square region with a side length ofM. The remaining attributes are as follows:(a)
All nodes are randomly distributed and fixed(b)
The intracluster data are sent by single-hop and the intercluster data are sent by multihop(c)
A node knows its residual energy but does not know where it is(d)
Every node has a different identity and can be a CH(e)
There is only one BS in the WSN and the BS is fixedThe transmission power can be adaptive based on the distance to receiver. By comparing the strength of the transmitted and received signals, a receiver can calculate the distance to the sender. Data aggregation is performed to reduce energy consumption. The data from nodes in a same cluster can be aggregated, while data from different clusters cannot be aggregated.ETx represents energy consumption of sending l bits data, and ERx represents energy consumption of receiving. The formula is as follows:(2)ETxl,d=l×Eelec+l×εfs×d2,d<dcorssover,l×Eelec+l×εmp×d4,d≥dcorssover,ERxl=l×Eelec,where d is the transmission distance. Eelec, εfs, εmp, and dcorssover are constants, where Eelec is the energy dissipated per bit to run the transceiver circuitry, εfs is the amplifier energy parameters corresponding to the free space channel model, εmp is the amplifier energy parameters corresponding to the multipath channel mode, and dcorssover is the distance threshold [15]. The values of experiment are shown in Table 1.Table 1
Simulation parameters.
ParameterValueεfs10 pJ/bit/m2εmp0.0013 pJ/bit/m4Eelec50 nJ/bitdcorssover87 m


## 4. The Approach

In CUCMA, some nodes are selected to become CHs. Each other node joins a cluster, and every cluster has only one CH. The CHs are reselected in each round.


### 4.1. Cluster Radius

In general, the uniform distribution of CHs may prolong the lifetime. A CH will forward more data if it is closer to BS, so the CHs which are closer to BS consume greater energy for intercluster communications. A CH also consumes energy to receive, aggregate, and transmit data. The intracluster energy consumption of a CH is usually high if the cluster has many nodes. To balance the loads of CHs, we reduce the number of nodes in the clusters those are close to BS. That means the clusters which are close to BS have smaller cluster area. In other words, the CR decreases while the distance to BS reduces.Ri presents the CR of node i. References [19, 29] give the formula of Ri which is as follows:(3)Ri=1−c×dmax−dtoBSdmax−dminRmax,where Rmax is the maximum CR which is predefined, dtoBS is the distance between i and BS, c is a constant between 0 and 1, the optimal value of c is 0.3 [29], and dmax is the maximum distance from a node to BS while dmin is the minimum distance.Since nodes are randomly distributed, a smaller cluster does not always have fewer nodes, so energy consumption balance cannot be fully realized usingRi calculated by Equation (3).We should distribute more CHs in the region which has more nodes and fewer in the region which has fewer nodes. To realize the rational distribution of CHs, we resizeRi according to ni. Here, ni is the number of nodes whose distances to i are less than Ri. We set ne as the average number of nodes in a circle with a radius of Ri and ne=πRi2/SN. Here, S is the area of the WSN and N is the number of all nodes. If ni=ne, we will not resize Ri; otherwise, Ri should be resized.Ifni>ne, lots of nodes are around i, so we decrease Ri to distribute more CHs in the region. As Ri decreases, ni is also decreased and the size of a cluster is decreased, so the energy consumption of intracluster decreases. However, due to the smaller coverage of a cluster, the network may have more CHs to cover all nodes. Because CHs will consume energy to form clusters and forward data, more CHs may increase energy consumption [30].In Figure1(a), the original size of a cluster is indicated by a solid circle whose radius is Ri and the dotted circle means the resized cluster whose resized CR (RCR) is Ri′. dtoi (Ri′≤dtoi≤Ri) is the distance from i to a node that is in the ring whose outer diameter is Ri and inner diameter is Ri′. The distribution of dtoi is(4)Fx=Pdtoi<x=π×x2−Ri'2π×Ri2−Ri'2,where Ri′≤x≤Ri. The density function is(5)fx=2xRi2−Ri′2.Figure 1
ResizingRi: (a) decreasing Ri; (b) increasing Ri.
(a)(b)The expectation ofdtoi is Edtoi given as follows:(6)Edtoi=∫Ri′Rixfxdx=23×Ri3−Ri′3Ri2−Ri′2.The expectation ofdtoi2 is Edtoi2 given as follows:(7)Edtoi2=∫Ri′Rix2fxdx=Ri2+Ri′22.We assume the data lengths are alll bits. According to Equation (2), the energy consumption of a node in the ring sending l bits data to i is(8)E1=l×Eelec+l×εfs×Ri2+Ri′22.If we decrease the radius toRi′, a node in the ring may select another CH. We assume that the RC of the newly chosen CH is Ri. The expectation of squared distance between a node in the circle with the radius of Ri to the center is Ri2/2 according to Equation (7), so the expectation energy consumption of sending l bits data to the new CH is(9)E2=l×Eelec+l×εfs×Ri22.We believe the number of nodes in the ring isni×Ri2−Ri′2/Ri2, so if the RC decreases to Ri′, the decreased energy consumption is(10)Edec=l×εfs×ni×Ri2−Ri′2Ri2×Ri′22.Because of the reduction area of the cluster, the network may have more CHs and the number of more CHs isRi2−Ri′2/Ri2. If a CH sends cluster-form-message and forwards data with the distance of Rmax, the increased energy consumption is(11)Einc=2×l×Eelec+l×εfs×Rmax2×Ri2−Ri′2Ri2.LetEdec=Einc, so(12)Ri′=4×Eelec+εfs×Rmax2εfs×ni.Ifni<ne, few nodes are around i, so we increase Ri to distribute fewer CHs in the region as shown in Figure 1(b). The derivation process of Ri′ is omitted.In short, RC is preliminarily calculated according to Equation (3) and then further calculated by the number of around nodes based on Equation (12).


### 4.2. CHs Distribution

The distances among CHs should be moderate. If CHs are far from each other, the intercluster energy consumption is large due to the far distance. If CHs are close to each other, the energy consumption of clustering is large because more CHs will be selected to cover all nodes.The ideal clusters distribution is shown in Figure2. In Figure 2, a square represents the area of a cluster and each point at the center of a square represents a CH. m and n are two adjacent CHs, and their resized cluster radii are Rm and Rn. The distance between m and n is Rm+Rn/2.Figure 2
Ideal CHs distribution.Because of the randomness in selecting CHs, the actual distribution of CHs is different. In Figure3, j is a selected CH. Its resized cluster radii are Rj, and the square represents the area of its cluster. We limit the minimum distance between two CHs to avoid CHs become too close to each other. In Figure 3, Rα is the radius of circle α whose center is j. The nodes except j in circle α cannot become CHs, so the distance between j and any other CH is more than Rα, so two CHs will not be too close.Figure 3
New CH selection around a selected CH.IfRα is too small, CHs may be still close to each other. If Rα is too large, fewer CHs will be selected around j because some nodes which are close to j lose the chances to become CHs. That means two CHs may be far from each other, and we set another circle to avoid this distribution. In Figure 3, Rβ is the radius of circle β whose center is j also. We try to select new CHs in the ring whose external diameter is Rβ and inner diameter is Rα. Each node has different Rα and Rβ because their resized cluster radius is different.k is a node around j. Its resized cluster radius is Rk, and the distance to j is dtoCH. To determine whether k becomes a CH, Rα and Rβ should be calculated to decide whether dtoCH is appropriate.The expectation distance from a node in the ring toj is 2/3×Rβ3−Rα3/Rβ2−Rα2 according to Equation (6), and the expectation distance should be Rj+Rk/2, so we get the following equation:(13)23×Rβ3−Rα3Rβ2−Rα2=Rj+Rk2.In Figure3, u and z are the intersections of β and the extended line of a side of the cluster. v and s are the intersections of α and the line zj and uj. A ring is made up of line vu and zs and arc uz and sv. The coverage of cluster k is a square whose area is 2Rk2 that means a CH should be selected among the nodes in the square, so if the area of the ring is 2Rk2, there may be a CH in the ring, and then Equation (14) is tenable.(14)Rβ2−Rα2×cos−1Rj2×Rβ=2×Rk2.According to Equation (13) and Equation (14), we can calculate Rα and Rβ.If a node becomes a CH, it will broadcast a cluster-form-message with its ID and resize cluster radius to other nodes. If any node receives the message, it should calculatedtoCH and Rα according to the CHs’ resized cluster radius and its resized cluster radius. If Rα ≥ dtoCH, the node should not become a CH; otherwise, it still has the chance. Obviously, a node with bigger resized cluster radius is more likely to lose the chance.


### 4.3. Distance Competition

The numbers of nodes in clusters are similar by resized cluster radius, but the total distance from the nodes in a cluster to their CH is different among clusters. We assume that∑​dtoi2 is the sum of squares of the distances from i to all nodes in a circle with a radius of Rj′. Obviously, diminution of ∑​dtoi2 can decrease the intracluster communication energy consumption if i becomes a CH, so a node with fewer ∑​dtoi2 should have more chance to be a CH. The expectation of ∑​dtoi2 is ni′×Ri′2/2 according to Equation (7). Here, ni′ is the number of nodes whose distances to i are less than Ri′. We assume ti is the waiting time of i, and ti is calculated as follows:(15)ti=ran×t0+MINN×∑​dtoi2ni′×Ri′2,N2×t0,ifEi≥Emax2,∞,else,where t0 is a given time and ran is a random number which is between 0 and 1. ran is used to ensure that waiting times are different among all nodes. Emax is the max residual energy of all nodes, and Ei is the residual energy of i. Obviously, ti≤1+N/2×t0.When selecting CHs, a node should wait forti before it becomes a CH. During waiting, once a node receives a cluster-form-message, it calculates Rα and dtoCH. The node loses the chance to become a CH if Rα ≥ dtoCH; else it keeps on waiting. When waiting time is over, if it still has the chance, it becomes a CH.When selecting CHs,i will always receive information before ti reached. When ti is over, if CHs selection is still going on, i will become a CH and send a cluster-form-message to other nodes. The CHs selection will last 1+N/2×t0.


### 4.4. The Steps of CUCMA

In this section, we proposed a competition-based unequal clustering multihop approach. In this approach, each node calculates the distance from other nodes through broadcast information and reports it to a BS. The BS gives the distance expectation and threshold, starts a CH selection timer, and optimizes the selection of a CH according to the distance and residual energy information within the specified time to seek the best nodes to be CHs for this round, which can be described as follows:Step 1. At beginning, each node sends a message using specific transmission power. The message includes energy and ID of the node. Each node receives these messages and calculates the distances to other nodes.Step 2. BS receives these messages and findsEmax, dmax, and dmin, then broadcasts them with maximum transmission power, and starts 1+N/2×t0 timing.Step 3. Every node receives the message sent by BS, calculatesR′, generates ran, calculates ti, and starts timing.Step 4. While timing, if a node receives a cluster-form-message, it calculatesRα and dtoCH. The node loses the chance to become a CH if Rα ≥ dtoCH, else it keeps on waiting. When waiting time is over, if the CHs selection is still going on, it becomes a CH. Then, the new CH broadcasts a cluster-form-message with its ID and R′.Step 5. When1+N/2×t0 is up, BS sends a CHs-selection-end-message to end the CHs selection.Step 6. Each non CH node sends a join-in-message to the nearest CH. The message includes the IDs of the CH and itself. The CH receives the messages and replies an acknowledge-message to finish clustering.Step 7. Each node gathers information and then sends data with residual energy information to its CHs. Each CH receives and aggregates the data and finds the maximum residual energy in the cluster. CHs transmit the data to BS by multihop. At the end of a round, go back to step 2.Nodes compete for CHs by calculating their own distance and energy information. By optimizing CH selection, energy consumption is reduced and network lifetime is improved. However, this method is not suitable for WSNs with multiple BSs and networks with energy harvesting function.


## 4.1. Cluster Radius

In general, the uniform distribution of CHs may prolong the lifetime. A CH will forward more data if it is closer to BS, so the CHs which are closer to BS consume greater energy for intercluster communications. A CH also consumes energy to receive, aggregate, and transmit data. The intracluster energy consumption of a CH is usually high if the cluster has many nodes. To balance the loads of CHs, we reduce the number of nodes in the clusters those are close to BS. That means the clusters which are close to BS have smaller cluster area. In other words, the CR decreases while the distance to BS reduces.Ri presents the CR of node i. References [19, 29] give the formula of Ri which is as follows:(3)Ri=1−c×dmax−dtoBSdmax−dminRmax,where Rmax is the maximum CR which is predefined, dtoBS is the distance between i and BS, c is a constant between 0 and 1, the optimal value of c is 0.3 [29], and dmax is the maximum distance from a node to BS while dmin is the minimum distance.Since nodes are randomly distributed, a smaller cluster does not always have fewer nodes, so energy consumption balance cannot be fully realized usingRi calculated by Equation (3).We should distribute more CHs in the region which has more nodes and fewer in the region which has fewer nodes. To realize the rational distribution of CHs, we resizeRi according to ni. Here, ni is the number of nodes whose distances to i are less than Ri. We set ne as the average number of nodes in a circle with a radius of Ri and ne=πRi2/SN. Here, S is the area of the WSN and N is the number of all nodes. If ni=ne, we will not resize Ri; otherwise, Ri should be resized.Ifni>ne, lots of nodes are around i, so we decrease Ri to distribute more CHs in the region. As Ri decreases, ni is also decreased and the size of a cluster is decreased, so the energy consumption of intracluster decreases. However, due to the smaller coverage of a cluster, the network may have more CHs to cover all nodes. Because CHs will consume energy to form clusters and forward data, more CHs may increase energy consumption [30].In Figure1(a), the original size of a cluster is indicated by a solid circle whose radius is Ri and the dotted circle means the resized cluster whose resized CR (RCR) is Ri′. dtoi (Ri′≤dtoi≤Ri) is the distance from i to a node that is in the ring whose outer diameter is Ri and inner diameter is Ri′. The distribution of dtoi is(4)Fx=Pdtoi<x=π×x2−Ri'2π×Ri2−Ri'2,where Ri′≤x≤Ri. The density function is(5)fx=2xRi2−Ri′2.Figure 1
ResizingRi: (a) decreasing Ri; (b) increasing Ri.
(a)(b)The expectation ofdtoi is Edtoi given as follows:(6)Edtoi=∫Ri′Rixfxdx=23×Ri3−Ri′3Ri2−Ri′2.The expectation ofdtoi2 is Edtoi2 given as follows:(7)Edtoi2=∫Ri′Rix2fxdx=Ri2+Ri′22.We assume the data lengths are alll bits. According to Equation (2), the energy consumption of a node in the ring sending l bits data to i is(8)E1=l×Eelec+l×εfs×Ri2+Ri′22.If we decrease the radius toRi′, a node in the ring may select another CH. We assume that the RC of the newly chosen CH is Ri. The expectation of squared distance between a node in the circle with the radius of Ri to the center is Ri2/2 according to Equation (7), so the expectation energy consumption of sending l bits data to the new CH is(9)E2=l×Eelec+l×εfs×Ri22.We believe the number of nodes in the ring isni×Ri2−Ri′2/Ri2, so if the RC decreases to Ri′, the decreased energy consumption is(10)Edec=l×εfs×ni×Ri2−Ri′2Ri2×Ri′22.Because of the reduction area of the cluster, the network may have more CHs and the number of more CHs isRi2−Ri′2/Ri2. If a CH sends cluster-form-message and forwards data with the distance of Rmax, the increased energy consumption is(11)Einc=2×l×Eelec+l×εfs×Rmax2×Ri2−Ri′2Ri2.LetEdec=Einc, so(12)Ri′=4×Eelec+εfs×Rmax2εfs×ni.Ifni<ne, few nodes are around i, so we increase Ri to distribute fewer CHs in the region as shown in Figure 1(b). The derivation process of Ri′ is omitted.In short, RC is preliminarily calculated according to Equation (3) and then further calculated by the number of around nodes based on Equation (12).


## 4.2. CHs Distribution

The distances among CHs should be moderate. If CHs are far from each other, the intercluster energy consumption is large due to the far distance. If CHs are close to each other, the energy consumption of clustering is large because more CHs will be selected to cover all nodes.The ideal clusters distribution is shown in Figure2. In Figure 2, a square represents the area of a cluster and each point at the center of a square represents a CH. m and n are two adjacent CHs, and their resized cluster radii are Rm and Rn. The distance between m and n is Rm+Rn/2.Figure 2
Ideal CHs distribution.Because of the randomness in selecting CHs, the actual distribution of CHs is different. In Figure3, j is a selected CH. Its resized cluster radii are Rj, and the square represents the area of its cluster. We limit the minimum distance between two CHs to avoid CHs become too close to each other. In Figure 3, Rα is the radius of circle α whose center is j. The nodes except j in circle α cannot become CHs, so the distance between j and any other CH is more than Rα, so two CHs will not be too close.Figure 3
New CH selection around a selected CH.IfRα is too small, CHs may be still close to each other. If Rα is too large, fewer CHs will be selected around j because some nodes which are close to j lose the chances to become CHs. That means two CHs may be far from each other, and we set another circle to avoid this distribution. In Figure 3, Rβ is the radius of circle β whose center is j also. We try to select new CHs in the ring whose external diameter is Rβ and inner diameter is Rα. Each node has different Rα and Rβ because their resized cluster radius is different.k is a node around j. Its resized cluster radius is Rk, and the distance to j is dtoCH. To determine whether k becomes a CH, Rα and Rβ should be calculated to decide whether dtoCH is appropriate.The expectation distance from a node in the ring toj is 2/3×Rβ3−Rα3/Rβ2−Rα2 according to Equation (6), and the expectation distance should be Rj+Rk/2, so we get the following equation:(13)23×Rβ3−Rα3Rβ2−Rα2=Rj+Rk2.In Figure3, u and z are the intersections of β and the extended line of a side of the cluster. v and s are the intersections of α and the line zj and uj. A ring is made up of line vu and zs and arc uz and sv. The coverage of cluster k is a square whose area is 2Rk2 that means a CH should be selected among the nodes in the square, so if the area of the ring is 2Rk2, there may be a CH in the ring, and then Equation (14) is tenable.(14)Rβ2−Rα2×cos−1Rj2×Rβ=2×Rk2.According to Equation (13) and Equation (14), we can calculate Rα and Rβ.If a node becomes a CH, it will broadcast a cluster-form-message with its ID and resize cluster radius to other nodes. If any node receives the message, it should calculatedtoCH and Rα according to the CHs’ resized cluster radius and its resized cluster radius. If Rα ≥ dtoCH, the node should not become a CH; otherwise, it still has the chance. Obviously, a node with bigger resized cluster radius is more likely to lose the chance.


## 4.3. Distance Competition

The numbers of nodes in clusters are similar by resized cluster radius, but the total distance from the nodes in a cluster to their CH is different among clusters. We assume that∑​dtoi2 is the sum of squares of the distances from i to all nodes in a circle with a radius of Rj′. Obviously, diminution of ∑​dtoi2 can decrease the intracluster communication energy consumption if i becomes a CH, so a node with fewer ∑​dtoi2 should have more chance to be a CH. The expectation of ∑​dtoi2 is ni′×Ri′2/2 according to Equation (7). Here, ni′ is the number of nodes whose distances to i are less than Ri′. We assume ti is the waiting time of i, and ti is calculated as follows:(15)ti=ran×t0+MINN×∑​dtoi2ni′×Ri′2,N2×t0,ifEi≥Emax2,∞,else,where t0 is a given time and ran is a random number which is between 0 and 1. ran is used to ensure that waiting times are different among all nodes. Emax is the max residual energy of all nodes, and Ei is the residual energy of i. Obviously, ti≤1+N/2×t0.When selecting CHs, a node should wait forti before it becomes a CH. During waiting, once a node receives a cluster-form-message, it calculates Rα and dtoCH. The node loses the chance to become a CH if Rα ≥ dtoCH; else it keeps on waiting. When waiting time is over, if it still has the chance, it becomes a CH.When selecting CHs,i will always receive information before ti reached. When ti is over, if CHs selection is still going on, i will become a CH and send a cluster-form-message to other nodes. The CHs selection will last 1+N/2×t0.


## 4.4. The Steps of CUCMA

In this section, we proposed a competition-based unequal clustering multihop approach. In this approach, each node calculates the distance from other nodes through broadcast information and reports it to a BS. The BS gives the distance expectation and threshold, starts a CH selection timer, and optimizes the selection of a CH according to the distance and residual energy information within the specified time to seek the best nodes to be CHs for this round, which can be described as follows:Step 1. At beginning, each node sends a message using specific transmission power. The message includes energy and ID of the node. Each node receives these messages and calculates the distances to other nodes.Step 2. BS receives these messages and findsEmax, dmax, and dmin, then broadcasts them with maximum transmission power, and starts 1+N/2×t0 timing.Step 3. Every node receives the message sent by BS, calculatesR′, generates ran, calculates ti, and starts timing.Step 4. While timing, if a node receives a cluster-form-message, it calculatesRα and dtoCH. The node loses the chance to become a CH if Rα ≥ dtoCH, else it keeps on waiting. When waiting time is over, if the CHs selection is still going on, it becomes a CH. Then, the new CH broadcasts a cluster-form-message with its ID and R′.Step 5. When1+N/2×t0 is up, BS sends a CHs-selection-end-message to end the CHs selection.Step 6. Each non CH node sends a join-in-message to the nearest CH. The message includes the IDs of the CH and itself. The CH receives the messages and replies an acknowledge-message to finish clustering.Step 7. Each node gathers information and then sends data with residual energy information to its CHs. Each CH receives and aggregates the data and finds the maximum residual energy in the cluster. CHs transmit the data to BS by multihop. At the end of a round, go back to step 2.Nodes compete for CHs by calculating their own distance and energy information. By optimizing CH selection, energy consumption is reduced and network lifetime is improved. However, this method is not suitable for WSNs with multiple BSs and networks with energy harvesting function.


## 5. Simulation Results and Analysis

CUCMA is compared with LEACH, ACCA, EAUCA, and CEECR. LEACH is a typical clustering protocol. ACCA, EAUCA, and CEECR are multihop and unequal clustering approach. These approaches have been simulated by NS2 in different scenarios.Scenario 1. 200 nodes are randomly distributed in a square field, and the length of side is 400 m. BS is at (20 m, 200 m).Scenario 2. 200 nodes are randomly dispersed in a square field, and the length of side is 400 m. BS is at (200 m, 0 m).Scenario 3. 300 nodes are randomly dispersed in a square field, and the length of side is 400 m. BS is at (200 m, 200 m).Scenario 4. 200 nodes are randomly dispersed in a square field, and the length of side is 600 m. BS is at (300 m, 300 m).Figure4 shows the distribution of nodes. Four simulation scenarios are shown in Figure 4. Scenario 1 and scenario 2 compare the distribution of nodes under different BS locations. Scenario 3 increases the number of nodes in scenario 1 and scenario 2 by 100. Scenario 4 expands the simulation area, and the horizontal and vertical coordinates are expanded by 1.5 times, respectively. According to Reference [28], other parameters are shown in Table 1.Figure 4
Nodes distribution: (a) scenario1; (b) scenario2; (c) scenario3; (d) scenario4.
(a)(b)(c)(d)The whole network energy consumptions in 20 rounds are shown in Figure5. LEACH consumes the most energy, and the energy consumptions in different rounds have more variant than others. There are two main reasons for this. One is that the CHs communicate with BS directly which costs more energy if the average distance from all nodes to the BS is far such as scenarios 2 and 4, so LEACH is not suitable for large WSNs. Another is that the CHs are selected without any standard metrics.Figure 5
Energy consumption: (a) scenario 1; (b) scenario 2; (c) scenario 3; (d) scenario 4.
(a)(b)(c)(d)The other four approaches are clustering and multihop. When the distance increases, the energy consumptions also increase, but the increases are obviously lower than those of LEACH, so ACCA, EAUCA, CEECR, and CUCMA are suitable for large WSNs.ACCA selects the nodes with more around nodes and smaller average distance to around nodes to become CHs to reduce the intracluster distance for a cluster which in turn reduces network energy consumption.EAUCA proposes an energy-aware unequal clustering algorithm to select CHs based on remaining energy and a node’s degree in a competition radius and uses low degree nodes as relay nodes to reduce the energy consumption of CHs and prolong the network life cycle [27].CEECR uses a central control algorithm to create a better set of CHs with less mobility and more energy. Furthermore, the optimal CH is selected for a detached node depending on the combined weights [28].In CUCMA, CHs have appropriate distances to around nodes to reduce intracluster energy consumption and appropriate distances to around CHs to reduce intercluster energy consumption. The energy consumption of CUCMA is stable and relatively low as shown in Figure5. The distribution of the CHs is better than that of the other four approaches, and the fluctuation of energy consumptions is most smooth.The simulation results of lifetime are shown in Figure6. We use FND (First Node Dies), HND (Half of the Nodes Dies), and LND (Last Node Dies) metrics as the network lifetime [24].Figure 6
Network lifetime: (a) FND; (b) HND; (c) LND.
(a)(b)(c)LEACH has the worst result as expected because of its higher energy consumption. LEACH does not select cluster heads according to the residual energy. If a node with low residual energy has become a CH, it tends to die, so the FND of LEACH is very earlier especially when the CH consumes a lot of energy in a certain round such as scenarios 2 and 4. The other four approaches select CHs according to the residual energy, and a node with low residual energy will not become a CH, so the FND is postponed.ACCA, EAUCA, CEECR, and CUCMA are all clustering approaches, and they balance the energy consumption of the CHs with different distances to the BS. Although the distribution of the nodes is more appropriate than that of LEACH, ACCA, EAUCA, and CEECR, they also have their flaws. The common flaw is that the CHs may be too far from each other. Although there are more cluster heads in the node dense area, the minimum distance between CHs is fixed, so the distribution of CHs is still defective in the node dense region. CUCMA resizes CRs according to the number of around nodes, so that the distribution of CHs is appropriate, and selects the nodes near the center of their clusters as CHs, which is suitable for the network environment with uneven distribution of nodes. CUCMA balances the loads among CHs and prolongs the network lifetime.


## 6. Conclusion and Future Works

We propose an unequal clustering multihop clustering approach for WSN. Selection criteria are more around nodes and closer to the around nodes. CUCMA calculates the resized cluster radius according to the number of around nodes, then selects CHs according to the distances to around nodes, and restricts the minimum distance between two CHs. By these measures, the CHs may have appropriate distribution. Thus, CUCMA balances the loads of CHs and reduces the energy consumption. Aiming at the limitations of the proposed method, further improvements may be obtained by exploring a more layer architecture and using better routing approach and so on. We can also consider the clustering optimization method which combines fixed nodes and mobile nodes.



---

*Source: 9994136-2021-06-21.xml*