Energy-Balanced Uneven Clustering Protocol Based on Regional Division for Sensor Networks

Abstract

In view of the unbalanced energy consumption of traditional cluster-based sensor networks, this paper proposes a type of uneven clustering protocol in data collection. The network is divided into inner and outer regions according to the distance between nodes and the base station. The inner region is consisted of several layers and nodes in outer region are deployed in grids of different sizes. Sensor data is collected by nodes in outer region and then is be transmitted to the inner region. Nodes in the inner region do data fusion and forward data from the lower layer to the higher one. Simulation results show that, compared with MTP and CDFUD, the proposed algorithm performs well in balance of energy consumption and could effectively prolong the network lifetime.

1. Introduction

Due to the dense deployment of sensor networks, sensory data tended to have larger redundancy in time and space which not only increase the cost of transmission and processing but also affect the expansion of its application [1, 2]. In the age of big data and ubiquitous network, it has been one of the key technologies to further improve the execution efficiency as well as the quality of sensory data with the help of data fusion and data aggregation in wireless sensor networks (WSNs for short).

On the other hand, energy consumption problem is also one of the hotspots in WSNs. How to achieve efficient energy management and optimization on the sensor nodes with weak computation and communication capabilities as well as limited power reserve is also a key problem which could greatly improve the network performance.

For most of the existing data fusion algorithms, they always focus on the optimization of energy consumption in communication between nodes but ignore the cost of energy consumption in data fusion in the dense deployment wireless sensor networks [3]. In addition, the large amount and various types of sensor data have greatly increase the overhead of calculating and processing of the node. Therefore, calculating become another source of energy consumption [4].

Based on the regional cluster network structure, this paper analyzes the energy consumption during data transmission and fusion process and put forward a type of energy-balanced data fusion method which is efficiently decreasing the energy consumption of the whole network.

The rest of the paper is organized as follows. The related works and the network model are described in Sections 2 and 3, respectively. In Section 4, we analyse the energy consumption of nodes in inner region and outer region. Experimental results are shown in the fifth section and the conclusion is provided in the last section.

2. Related Works

There are two types of data gathering methods in WSNs: the routing-driven method and the fusion-driven one [5]. In routing-driven method, sensor data is transmitted hop by hop through the shortest path and data from different sources will be fused. However, the fusion process depends only on the data dependency in fusion-driven method and the efficiency of data gathering of this method has nothing to do with node deployment [6]. In this paper, a type of routing-driven data gathering method based on uneven clustering and regional division is proposed.

LEACH [7] is the first data gathering architecture for wireless sensor networks that achieves low energy dissipation and latency without sacrificing application-specific quality [8]. It uses a clustering architecture where each node in the cluster sends its data to a local cluster head. However, this mode is responsible for collecting data from all sensors in the cluster and sends them to the receiving end without data fusion, which not only reduces the bandwidth utilization but also increases energy consumption.

PEGASIS is an enhancement over LEACH [9]. Nodes are organized to form a chain, so that they need to communicate only with their closest neighbors. PEGASIS avoids cluster formation and only uses one node in a chain to transmit to the sink node instead of using multiple nodes. It reduces the energy consumption on transmission per round as the power draining is spread uniformly over all nodes. Nevertheless, PEGASIS presents a big delay for the most distant node in the chain, even if the clustering overhead is avoided.

Another kind of typical energy aware data gathering protocol is MTP (Multi-Tier Trace-Back Protocol) [10]. It selects one node with the most sufficient energy as well as the shortest distance to the base station (BS for short) as the relay node which could communicate with the BS directly. Other nodes could only transmit and fuse their data to the parent node in the upper layer. If the cluster head in MTP is far away from the BS, it will consume more energy during data gathering, fusing, and transmitting. On the other hand, according to MTP, nodes in the upper layer will also forward its data to their parent node even if the parent node is just in the lower layer. It not only increases the transmission cost but also reduces the reliability of the whole network.

Yue et al. proposed an uneven clustering algorithm based on grid, namely, CDFUD [11, 12] (Clustering Data Fusion Algorithm Based on Uneven Division). Sizes of the grids are different from each other according to their distance to the BS and the node with the maximal residual energy in each grid is chosen as the cluster head. Similar to LEACH, the cluster head in each gird transmit the data of its members as well as itself to BS with one hop. The main disadvantage of CDFUD is that the cluster head consumes energy rapidly which causes unbalance energy consumption in the network.

K-Means [13] Data Relay Clustering algorithm is developed to group the sensor nodes for energy efficient data communication. K arbitrary points are picked as the cluster head by the sink node. Cluster members are obtained for each CH based on distance metric. Then, in each CH, data aggregation process is done for limiting the energy spent in transmission. Although it reduces the communication overhead, it also reduces the number of nodes transmitting data to sink node and unable to collect enough information which we need.

TMMDF [14] eliminates negligent errors by Dixon method to obtain a valid observation data and uses the triangle module operator to assign weights of each sensor data. Finally, it gets the fusion estimate values. Although data delay of this method is greatly increased, it is not an efficient method for large-scale data processing.

Based on the study above, an energy-balanced uneven clustering protocol (EUCP) is proposed in this paper. According to the distance between nodes and BS, it divides regions into clusters with different sizes. And the size of each cluster as well as the number of nodes is related to the energy consumption of each grid. Simulation results show that EUCP could effectively prolong the network lifetime and balance the whole network energy consumption.

3. Method Description

3.1. Network Model

As we know, in two-dimensional space, the communication and sensing area of one node is a circular whose center is the node itself [15]. Therefore, in EUCP, we assume that the shape of the network is also a circular. Moreover, it has been proved that clustered structure is suitable for data fusion in WSNs [16], so it is still be adopted in EUCP. However, in cluster-based WSNs, nodes which are far from BS undertake minor data fusion mission (the nodes on boundary of the network even do not need to fuse data), while nodes which are close to BS often receive and process more data. So, in EUCP, we adopt the hierarchical structure to design the whole network for data transmission and fusion.

The attenuation model of wireless signal can be divided into free-space model and multipath fading model [17], as shown in Figure 1. A sensor node consumes energy when it is generating local data, receiving data, transmitting data, or in standby mode [18]. The energy for generating one bit of data and the standby energy consumed by one node are assumed to be the same for all nodes which can always be ignored. For energy used in receiving and transmitting, we adopt the first order radio model described in [19]. We assume that $E_S(J,d)$ and $E_R(J)$ represent the energy consumption of sending module and receiving module, while $E_{\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{c}}$ is the unit energy consumption of sending and receiving circuits. The energy consumption of circuit is in direct proportion to the data package size, J. ${\mu }_{\mathrm{a}\mathrm{m}\mathrm{p}}$ is the constant parameter of signal amplifier, and $d_0$ is assumed as the unit of transmission distance. In general, $d_0$ is equal to the communication radius R of nodes. We assume that each node send c bit data package in its slot time and the distance of transmitting is d. Thus, the energy consumption of sending module is [18]

$$\begin{array}{cc}& E_s\left(J,d\right)=\left\{\begin{array}{cc}c{E}_{\text{elec}}+c{\mu }_{fs}{d}^{\mathrm{2}},\hfill & d<d_{\mathrm{0}},\hfill \\ c{E}_{\text{elec}}+c{\mu }_{\text{amp}}{d}^{\mathrm{4}},\hfill & d\ge d_{\mathrm{0}},\hfill \end{array}\right.\end{array}$$

(1)

and to receive this message, the radio expends

$$\begin{array}{cc}& E_R\left(J\right)=c{E}_{\text{elec}}.\end{array}$$

(2)

Figure 1

Energy consumption model for one node.

In EUCP, all the nodes are distributed uniformly in a circle area with radius D ( $D>d_0$ ), and the BS is in the network center. Based on the analysis above, signal attenuation will be more serious when the nodes spacing is greater than $d_0$ . So, we divide the network into inner region and outer region by the boundary of $d_0$ , as shown in Figure 2. The gray area in this graph is inner region and the white one is the outer region. Points in Figure 2 are the sensing nodes.

Figure 2

Network structure.

As shown in Figure 2, in the inner region, the distance between nodes and BS, is smaller than $d_0$ . According to (1), energy consumption of sending data is proportional to $d^2$ . As we know, nodes in outer region is a little far from BS. So the multihop transmission method is used [20] to relay data through nodes in inner region which will certainly increase the energy assumption and traffic load of nodes. Therefore, we further divide the inner region into k annular regions, called “inner rings.” We assume that nodes in ith inner ring only need to transmit data to nodes in $i-1$ th inner ring. After data fusion, data will eventually be transmitted to BS hop by hop. The widths of each inner ring are $d_1,d_2,\dots ,d_k$ .

In wireless network, signal quality is determined mainly by base station antennas. In general, we divide the circle region into three sector regions with covering angle $2\pi /3$ . As shown in Figure 2, considering the similarity of the three sector regions, we only take one of them as an example.

3.2. Circular Division in Inner Region

In EUCP, $R_S$ is defined as the sensing radius, as shown in Figures 3 and 4. The distribution density of nodes is defined as ρ. According to [21], to realize completely coverage in omnidirectional sensor networks, the maximum and minimum distribution density ${\rho }_{\mathrm{m}\mathrm{a}\mathrm{x}}$ and ${\rho }_{\mathrm{m}\mathrm{i}\mathrm{n}}$ are

$$\begin{array}{cc}& {\rho }_{\mathrm{m}\mathrm{a}\mathrm{x}}=\frac{\mathrm{2}}{\sqrt{\mathrm{3}}{R}_s^{\mathrm{2}}},\\ {\rho }_{\mathrm{m}\mathrm{i}\mathrm{n}}=\frac{\mathrm{2}}{\mathrm{3}\sqrt{\mathrm{3}}{R}_s^{\mathrm{2}}}.\end{array}$$

(3)

Figure 3

Distribution of nodes with maximum density.

Figure 4

Distribution of nodes with minimum density.

Obviously, when the density of nodes is higher than ${\rho }_{\mathrm{m}\mathrm{a}\mathrm{x}}$ , redundant nodes will exist. While when the density is lower than ${\rho }_{\mathrm{m}\mathrm{i}\mathrm{n}}$ , the hole will appear.

Without loss of generality, we assume $\rho =({\rho }_{\mathrm{m}\mathrm{a}\mathrm{x}}+{\rho }_{\mathrm{m}\mathrm{i}\mathrm{n}})/2$ . Therefore, in the inner region showed in Figure 5, the width $d_1$ of innermost ring satisfies the following:

$$\begin{array}{cc}& \rho \times \frac{\pi d_{\mathrm{1}}^{\mathrm{2}}}{\mathrm{3}}=n_{\mathrm{1}}.\end{array}$$

(4)

Figure 5

A similar structure of binary tree in the inner region.

$n_1$ is the total number of nodes in the innermost ring. In addition, to promote the efficiency of data fusion and reduce the workload of nodes around base station, we construct a similar structure of binary tree by connecting the nodes in inner region. Thus, in Figure 5, for the second layer of inner region, its width $d_2$ satisfies the following:

$$\begin{array}{cc}& \frac{\rho }{\mathrm{3}}\times \left[\pi {\left(d_{\mathrm{1}}+d_{\mathrm{2}}\right)}^{\mathrm{2}}-\pi d_{\mathrm{1}}^{\mathrm{2}}\right]=\mathrm{2}{n}_{\mathrm{1}}.\end{array}$$

(5)

Similarly, the width of kth layer of inner region satisfies

$$\begin{array}{cc}& \frac{\rho }{\mathrm{3}}\times \left[\pi {\left({\displaystyle \sum }_{i=\mathrm{1}}^k{d}_i\right)}^{\mathrm{2}}-\pi {\left({\displaystyle \sum }_{i=\mathrm{1}}^{k-\mathrm{1}}{d}_i\right)}^{\mathrm{2}}\right]={\mathrm{2}}^{k-\mathrm{1}}\times n_{\mathrm{1}}.\end{array}$$

(6)

Widths of all inner rings satisfy

$$\begin{array}{cc}& {\displaystyle \sum }_{i=\mathrm{1}}^k{d}_i=d_{\mathrm{0}}.\end{array}$$

(7)

In inner region, we group every two nodes in ith layer together and they choose one node in the $i-1$ th layer as a parent node. Therefore, the binary tree is constructed from the kth layer to the innermost layer, which is named as “data fusion binary tree.” To insure that two nodes in adjacent rings could communicate with each other, the communication radius $R_t$ of one node should be greater than the longest distance of two nodes in adjacent inner ring. In Figure 6, we assume the maximum distance is $d^{\prime }$ :

$$\begin{array}{l}{R}_t>d^{\prime }=\sqrt{d_{\mathrm{0}}^{\mathrm{2}}+{\left(d_{\mathrm{0}}-d_k\right)}^{\mathrm{2}}-\mathrm{2}{d}_{\mathrm{0}}\left(d_{\mathrm{0}}-d_k\right)\cos \frac{\mathrm{2}\pi }{\mathrm{3}}}\\ =\sqrt{\mathrm{3}{d}_{\mathrm{0}}^{\mathrm{2}}-\mathrm{3}{d}_{\mathrm{0}}{d}_k+d_k^{\mathrm{2}}}.\end{array}$$

(8)

Figure 6

The longest distance in adjacent ring.

3.3. Division of Outer Region Based on Uneven Clustering

In EUCP, nodes in outer region are far from BS, and the distance between them is longer than $d_0$ . Therefore, multiple hop transmission should be used. Moreover, the area of the outer region is much bigger than inner one. So we divide the outer region into a number of uneven-sized subsector regions, and each region is defined as a cluster, referring to the thought of GAF methods [22].

First, we divide the outer region into l annular regions, called “outer rings” and number them as layer $k+1$ , layer $k+2,\dots ,\mathrm{l}\mathrm{a}\mathrm{y}\mathrm{e}\mathrm{r}\hspace{0.17em}\hspace{0.17em}k+l$ . Then, each “outer ring” is divided into a number of small regions with angel θ. We call these small regions “subregions.” In EUCP, we divide each layer of the outer ring into w subregions, as shown in Figure 7. In Figure 7, $\theta =2\pi /3w$ , and w is equivalent to the number of nodes $n_k$ in the outermost layer of the inner region. According to this way, outer regions are divided into $l\times w$ subregions. The cluster head collect data from each node in a subregion and transmit it to the upper cluster heads hop by hop to nodes in inner regions.

Figure 7

Subregions in outer region.

From the analysis above, it is obvious that, in EUCP, each node in the subregion should communicate with each other in one hop. Taking the outermost subregion for example, the maximum distance of any two nodes is just the length of diagonals of this subregion. We assume the length of diagonals is $d^{\prime \prime }$ . Therefore, as shown in Figure 7, the communication radius $R_t$ needs to satisfy

$$\begin{array}{l}{R}_t>d^{\prime \prime }=\sqrt{D^{\mathrm{2}}+{\left(D-d_{k+\mathrm{1}}\right)}^{\mathrm{2}}-\mathrm{2}D\left(D-d_{k+l}\right)\cos \theta }\\ =\sqrt{\mathrm{2}{D}^{\mathrm{2}}+\mathrm{2}D{d}_{k+\mathrm{1}}+d_{k+l}^{\mathrm{2}}-\mathrm{2}D\left(D-d_{k+l}\right)\cos \frac{\mathrm{2}\pi }{\mathrm{3}{n}_k}}.\end{array}$$

(9)

Similar to LEACH, in the initial stage of clustering, nodes in subregion need to broadcast packets containing their ID number, residual energy, and coordinates $(X_i,Y_i)$ . The node with the maximum residual energy is selected as the cluster head. If there are two or more standards-compliant nodes, the nearest one is selected as the cluster head by comparing the Euclidean distance between them and the subregion center which balances the energy consumption of all nodes in the subregion.

After the first round of data fusion and transmission, the cluster heads will be reselected. The priority of node i in subregion is defined as p, as shown in the following:

$$\begin{array}{cc}& p=\alpha \times E_i+\frac{\beta }{d_{io}}+\frac{\gamma }{{\chi }_c}.\end{array}$$

(10)

$d_{io}$ is the distance between node i and the subregion center. ${\chi }_c$ is the number of times that node i is selected as a cluster head. α, β, γ are the constant parameters. The node with the maximum value p will be selected as the cluster head in the next round and the new cluster head needs to broadcast its identity to its neighbors in the subregion.

4. Analysis of Energy Consumption

4.1. Energy Consumption of Nodes in Inner Region

As mentioned above, a similar structure of binary tree is built in inner region whose root is the base station. Each node (except the leaf nodes) needs to fuse data collected by itself and its two child nodes before uploading, while leaf nodes collect the data from the corresponding cluster heads in outer region and transmit them to their parent nodes in $k-1$ th layer. The data fusion rate is η.

For a node in ith layer of the inner region, $Z_i$ is defined as the amount of its data needed to be uploaded in one round time. Thus, if $i<k$ , $Z_i$ is just the sum of the amount of data collected by itself (defined as G) and uploaded by its two child nodes. While for a node in kth layer, $Z_k$ is just the sum of the amount of data collected by itself and data uploaded by its corresponding cluster head in outer region (defined as $Q_{k+1}$ ):

$$\begin{array}{cc}& Z_k=G+Q_{k+\mathrm{1}},\\ Z_{k-\mathrm{1}}=G+\mathrm{2}\left(G+Q_{k+\mathrm{1}}\right),\\ Z_{k-\mathrm{2}}=G+\mathrm{2}\left(G+\mathrm{2}\left(G+Q_{k+\mathrm{1}}\right)\right)\eta ,\\ ⋮\end{array}$$

(11)

By using mathematic induction, we obtain

$$\begin{array}{l}{Z}_{k-a}={\displaystyle \sum }_{i=\mathrm{0}}^{a-\mathrm{1}}{\mathrm{2}}^{i}G{\eta }^i+{\mathrm{2}}^a\left(G+Q_{k+\mathrm{1}}\right){\eta }^{a-\mathrm{1}},\\ k-\mathrm{1}\ge a\ge \mathrm{1}.\end{array}$$

(12)

Thus, for each node in $k-a$ th layer, its energy consumption $E_{k-a}$ during one round time is

$$\begin{array}{cc}& E_{k-a}=E\left(T_{k-a}\right)+E\left(R_{k-a}\right)+E\left(F_{k-a}\right),\\ E\left(T_{k-a}\right)=Z_{k-a}\left(E_{\text{elec}}+{\mu }_{\text{fs}}{d}_{\left(k-a,k-a-\mathrm{1}\right)}^{\mathrm{2}}\right),\\ E\left(R_{k-a}\right)=\mathrm{2}{Z}_{k-a+\mathrm{1}}{E}_{\text{elec}},\\ E\left(F_{k-a}\right)=f\times Z_{k-a}.\end{array}$$

(13)

f is defined as the energy consumption of data fusion per bit and $d_{(k-a,k-a-1)}$ is the distance between a node in $k-a$ th layer and its parent in $k-a-1$ th layer. Therefore, this distance approximately satisfies

$$\begin{array}{cc}& d_{\left(k-a,k-a-\mathrm{1}\right)}=\mathrm{0.5}\left(d_{k-a}+d_{k-a-\mathrm{1}}\right).\end{array}$$

(14)

For nodes in kth layer, there is no need to do data fusion. So the energy consumption $E_k$ can be expressed as

$$\begin{array}{l}{E}_k=E\left(T_k\right)+E\left(R_k\right)\\ =\left(G+Q_{k+\mathrm{1}}\right)\left(E_{\text{elec}}+{\mu }_{\text{fs}}{d}_{\left(k,k-\mathrm{1}\right)}^{\mathrm{2}}\right)+Q_{k+\mathrm{1}}{E}_{\text{elec}}\\ =\left(G+\mathrm{2}{Q}_{k+\mathrm{1}}\right)E_{\text{elec}}+\left(G+Q_{k+\mathrm{1}}\right){\mu }_{\text{fs}}{d}_{\left(k,k-\mathrm{1}\right)}^{\mathrm{2}},\end{array}$$

(15)

since the number of nodes in each layer of the inner region satisfies geometric progression whose common ratio is 2. Based on the above analysis, the total energy consumption $E_{\mathrm{i}\mathrm{n}}$ of all nodes in inner region in one round time is

$$\begin{array}{cc}& E_{\text{in}}={\displaystyle \sum }_{a=\mathrm{1}}^{k-\mathrm{1}}{\mathrm{2}}^{k-a-\mathrm{1}}\times n_{\mathrm{1}}\times E_{k-a}+E_k.\end{array}$$

(16)

4.2. Energy Consumption of Nodes in Outer Region

4.2.1. Energy Consumption of Data Fusion for the Cluster Head

We take a subregion in $k+j$ th layer of the outer region as an example to analyze the energy consumption of nodes. It is assumed that data fusion is finished by the cluster head of each subregion and the data fusion rate is still η. Thus, for each cluster head in the $k+j$ th layer ( $j<l$ ), the amount of data $Q_{k+j}$ after one round of data fusion is

$$\begin{array}{cc}& Q_{k+j}=\left(\rho \times S_{k+j}\times G+Q_{k+j+\mathrm{1}}\right)\times \eta .\end{array}$$

(17)

And the energy consumption on data fusion $E(F_{k+j})$ for each cluster head is

$$\begin{array}{cc}& E\left(F_{k+j}\right)=\left(\rho \times S_{k+j}\times G+Q_{k+j+\mathrm{1}}\right)\times f.\end{array}$$

(18)

Therefore, for the cluster head in the $k+l$ th layer, we obtain

$$\begin{array}{cc}& Q_{k+l}=\rho \times S_{k+l}\times G\times \eta ,\\ E\left(F_{k+l}\right)=\rho \times S_{k+l}\times G\times f.\end{array}$$

(19)

$S_{k+j}$ and $S_{k+l}$ are defined as area of the subregion in $k+j$ th and $k+l$ th layers, respectively. By the analysis above, we obtain

$$\begin{array}{cc}& S_{k+j}=\frac{\mathrm{2}\pi }{\mathrm{3}w}\times \pi \left[{\left({\displaystyle \sum }_{i=\mathrm{1}}^{k+j}{d}_i\right)}^{\mathrm{2}}-{\left({\displaystyle \sum }_{i=\mathrm{1}}^{k+j-\mathrm{1}}{d}_i\right)}^{\mathrm{2}}\right],\\ S_{k+l}=\frac{\mathrm{2}\pi }{\mathrm{3}w}\times \pi \left[D^{\mathrm{2}}-{\left({\displaystyle \sum }_{i=\mathrm{1}}^{k+l-\mathrm{1}}{d}_i\right)}^{\mathrm{2}}\right].\end{array}$$

(20)

4.2.2. Energy Consumption of Transmission for the Cluster Head and Its Members

Since nodes are uniformly distributed, for each subregion in the $k+j$ th layer, it is assumed that the average distance between cluster members and the cluster head is one-half length of its diagonal (defined as $d_{k+j}^{\prime \prime }$ ). Therefore, the total energy consumption of transmission for all cluster members in this subregion (defined as $E_1(T_{k+j})$ ) is

$$\begin{array}{l}{E}_{\mathrm{1}}\left(T_{k+j}\right)\\ =\left[G\times E_{\text{elec}}+G\times {\mu }_{\text{fs}}\times {\left(\mathrm{0.5}{d}_{k+j}^{\prime \prime }\right)}^{\mathrm{2}}\right]\left(\rho \times S_{k+j}-\mathrm{1}\right).\end{array}$$

(21)

In the equation,

$$\begin{array}{l}{d}_{k+j}^{\prime \prime }\\ =\sqrt{{\left({\displaystyle \sum }_{i=\mathrm{1}}^{k+j}{d}_i\right)}^{\mathrm{2}}+{\left({\displaystyle \sum }_{i=\mathrm{1}}^{k+j-\mathrm{1}}{d}_i\right)}^{\mathrm{2}}-\mathrm{2}{\displaystyle \sum }_{i=\mathrm{1}}^{k+j}{d}_i{\displaystyle \sum }_{i=\mathrm{1}}^{k+j-\mathrm{1}}{d}_i\cos \frac{\mathrm{2}\pi }{\mathrm{3}{n}_k}}.\end{array}$$

(22)

In addition, each cluster head needs to transmit the fused data to the upper cluster head. These data are collected by cluster head itself as well as its members and uploaded by the cluster head in the lower layer. So the energy consumption of transmission for a cluster head in the $k+j$ th layer (defined as $E_2(T_{k+j})$ ) is

$$\begin{array}{l}{E}_{\mathrm{2}}\left(T_{k+j}\right)\\ =\left(G\times E_{\text{elec}}+G\times {\mu }_{\text{fs}}\times {D^{\mathrm{2}}}_{\left(k+j,k+j-\mathrm{1}\right)}\right)Q_{k+j}.\end{array}$$

(23)

$D_{(k+j,k+j-1)}$ is the distance between the two neighboring cluster heads in $k+j$ th layer and the $k+j-1$ th layer. In the worst case, $D_{(k+j,k+j-1)}$ is the length of diagonal of the sector combined by two neighboring subregions in $k+j$ th layer and $k+j-1$ th layer as follows:

$$\begin{array}{l}\text{MAX}\left(D_{\left(k+j,k+j-\mathrm{1}\right)}\right)\\ =\sqrt{{\left({\displaystyle \sum }_{i=\mathrm{1}}^{k+j}{d}_i\right)}^{\mathrm{2}}+{\left({\displaystyle \sum }_{i=\mathrm{1}}^{k+j-\mathrm{2}}{d}_i\right)}^{\mathrm{2}}-\mathrm{2}{\displaystyle \sum }_{i=\mathrm{1}}^{k+j}{d}_i{\displaystyle \sum }_{i=\mathrm{1}}^{k+j-\mathrm{2}}{d}_i\cos \frac{\mathrm{2}\pi }{\mathrm{3}{n}_k}}.\end{array}$$

(24)

For simplicity, we define

$$\begin{array}{cc}& D_{\left(k+j,k+j-\mathrm{1}\right)}=\mathrm{0.5}\left(d_{k+j}+d_{k+j-\mathrm{1}}\right).\end{array}$$

(25)

4.2.3. Energy Consumption of Receiving for the Cluster Head

For the cluster head in the $k+j$ th layer, its energy consumption on data receiving (defined as $E(R_{k+j})$ ) is mainly on receiving data of its members as well as the data upload by the lower cluster heads. So,

$$\begin{array}{cc}& E\left(R_{k+j}\right)=\left[\left(\rho \times S_{k+j}-\mathrm{1}\right)\times G+Q_{k+j-\mathrm{1}}\right]\times E_{\text{elec}}.\end{array}$$

(26)

While for the cluster head in $k+j$ th layer, its energy consumption on data receiving (defined as $E(R_{k+l})$ ) is

$$\begin{array}{cc}& E\left(R_{k+l}\right)=\left(\rho \times S_{k+l}-\mathrm{1}\right)\times G\times E_{\text{elec}}.\end{array}$$

(27)

Therefore, in one round time of data collection and fusion, the total energy consumption of nodes in outer region (defined as $E_{\mathrm{o}\mathrm{u}\mathrm{t}}$ ) is expressed as

$$\begin{array}{l}{E}_{\text{out}}\\ ={\displaystyle \sum }_{j=\mathrm{1}}^{l-\mathrm{1}}\left[E\left(F_{k+j}\right)+E_{\mathrm{1}}\left(T_{k+j}\right)+E_{\mathrm{2}}\left(T_{k+j}\right)+E\left(R_{k+j}\right)\right]\\ +E\left(F_{k+l}\right)+E_{\mathrm{1}}\left(T_{k+l}\right)+E_{\mathrm{2}}\left(T_{k+l}\right)+E\left(R_{k+l}\right).\end{array}$$

(28)

That is,

$$\begin{array}{l}{E}_{\text{out}}=\sum _{j=1}^{l-1}\{\left(\rho S_{k+j}G+Q_{k+j+1}\right)f\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+\left[G{E}_{\text{elec}}+G{\mu }_{\text{fs}}{\left({0.5}_{k+j}^{\text{'}\text{'}}\right)}^2\right]\left(\rho S_{k+j}-1\right)\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+\left(G{E}_{\text{elec}}+G{\mu }_{\text{fs}}{D}_{(k+j,k+j-1)}^2\right)Q_{k+j}\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+\left[\left(\rho S_{k+j}-1\right)G+Q_{k+j-1}\right]E_{\text{elec}}\}+\rho S_{k+l}Gf\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+\left[G{E}_{\text{elec}}+G{\mu }_{\text{fs}}{\left(0.5d_{k+l}^{\text{'}\text{'}}\right)}^2\right](\rho S_{K+l}-1)+(G{E}_{\text{elec}}\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}+G{\mu }_{\text{fs}}{D}_{(k+l,k+l-1)}^2)Q_{k+l}+(\rho S_{k+l}-1)G{E}_{\text{elec}}.\hfill \end{array}$$

(29)

To balance energy consumption, it is assumed that the energy consumption of nodes in each subregion of outer region is approximately equal as follows:

$$\begin{array}{cc}& E_{k+\mathrm{1}}\approx E_{k+\mathrm{2}}\approx \cdots \approx E_{k+j}\approx \cdots \approx E_{k+l}.\end{array}$$

(30)

In (30), we have

$$\begin{array}{cc}& E_{k+j}=E\left(F_{k+j}\right)+E_{\mathrm{1}}\left(T_{k+j}\right)+E_{\mathrm{2}}\left(T_{k+j}\right)+E\left(R_{k+j}\right).\end{array}$$

(31)

As for the multihop wireless sensor networks, it is well known that clusters near the center could receive more data than the clusters which are away from the center. Therefore, we have

$$\begin{array}{cc}& E\left(F_{k+j}\right)>E\left(F_{k+h}\right),j<h,\\ E\left(R_{k+j}\right)>E\left(R_{k+h}\right),j<h.\end{array}$$

(32)

To satisfy (30), we need

$$\begin{array}{l}{E}_{\mathrm{1}}\left(T_{k+j}\right)+E_{\mathrm{2}}\left(T_{k+j}\right)<E_{\mathrm{1}}\left(T_{k+h}\right)+E_{\mathrm{2}}\left(T_{k+h}\right),\\ j<h.\end{array}$$

(33)

That is,

$$\begin{array}{l}\left[G{E}_{\text{elec}}+G{\mu }_{\text{fs}}{\left(\mathrm{0.5}{d}_{k+j}^{\prime \prime }\right)}^{\mathrm{2}}\right]\left(\rho S_{k+j}-\mathrm{1}\right)\\ +\left(G{E}_{\text{elec}}+G{\mu }_{\text{fs}}{D}_{\left(k+j,k+j-\mathrm{1}\right)}^{\mathrm{2}}\right)Q_{k+j}\\ <\left[G{E}_{\text{elec}}+G{\mu }_{\text{fs}}{\left(\mathrm{0.5}{d}_{k+h}^{\prime \prime }\right)}^{\mathrm{2}}\right]\left(\rho S_{k+h}-\mathrm{1}\right)\\ +\left(G{E}_{\text{elec}}+G{\mu }_{\text{fs}}{D}_{\left(k+h,k+h-\mathrm{1}\right)}^{\mathrm{2}}\right)Q_{k+h},j<h.\end{array}$$

(34)

Through analysis of (34), we obtain $d_{k+j}<d_{k+h}$ . Therefore, the area of subregions in outer region is not of the same size. That is to say, subregion which is close to the edge of networks has bigger area. At last, the outer region is present as an uneven clustering structure.

5. Experimental Results and Analysis

To analyze the balance of energy consumption as well as the network lifetime during data collection process, we use the java language to build the data collection model and then put the initial values for each parameter into the program to calculate the values of energy consumption and their variance. This paper compares EUCP with MTP and CDFUD algorithm, respectively.

5.1. Performance of Data Collection in Inner Region

The width $d_0$ of the inner region is 122 m and it is divided into four layers. Data generated by each node is 1 bit in an unit of time, and the number of nodes in the first layer $n_1$ is 2; similarly, $n_2=4$ , $n_3=8$ , and $n_4=16$ . Parameters values of the inner region are shown in Table 1.

Table 1

Parameter values of the inner region.

Parameter	Symbol	Value	Unit
Width of layer 1	$$d_1$$	31.5	m
Width of layer 2	$$d_2$$	23	m
Width of layer 3	$$d_3$$	28.8	m
Width of layer 4	$$d_4$$	38.69	m
Energy consumption of wireless sending and receiving circuit	$$E_{\text{elec}}$$	50	nJ×b−1
Energy consumption of amplifier in free-space model	$${\mu }_{\text{fs}}$$	10	pJ×(b/m2)−1
Energy consumption of amplifier in multipath fading model	$${\mu }_{\text{amp}}$$	0.0013	pJ×(b/m4)−1
Energy consumption of fusion for one bit	F	$$\mathrm{1.67}\times {\mathrm{10}}^{-\mathrm{11}}$$	J×b−1

We set the fusion rate η to be 0.25, 0.5, 0.75, and 1.0, respectively, to analyze energy consumption on EUCP and MTP (including MTP₁, MTP₂, MTP₃, and MTP₄). MT ${\mathrm{P}}_i$ represent the running of MTP in the ith round.

According to MTP, during the ith round, nodes which is not in the ith layer need to fuse and transmit data to nodes in the ith layer hop by hop, while nodes in the ith layer transmit all of the data to a node with the maximal residual energy of this layer which will then directly transmits these data to BS.

As shown in Figure 8, for the same data fusion rate η, energy consumption of MTP₁ is a little more than EUCP. However, with the increasing of rounds, energy consumption of MTP is significantly higher than EUCP. In MTP₂, a node which has maximal residual energy in layer 2 communicates with BS directly. But before this, nodes in layer 1 should transmit data to the nodes in layer 2 which is far from BS. This mode will obviously cause the waste of energy, while in EUCP, nodes in layer 1 transmit data to BS after having collected all the data from other layers which could keep equal energy consumption in each round of data fusion as well as data forwarding and could prolong network lifetime.

Figure 8

Energy consumption of EUCP and MTP in one round of data fusion and transmission.

The inner region is divided into 4 layers and the energy consumption of each layer is $E_1$ , $E_2$ , $E_3$ , and $E_4$ , respectively. Figures 9, 10, 11, and 12 are the energy consumption of EUCP and MTP in different layers.

Figure 9

Energy consumption in each layer of MTP and EUCP ( $\eta =0.25$ ).

Figure 10

Energy consumption in each layer of MTP and EUCP ( $\eta =0.5$ ).

Figure 11

Energy consumption in each layer of MTP and EUCP ( $\eta =0.75$ ).

Figure 12

Energy consumption in each layer of MTP and EUCP ( $\eta =1$ ).

It is easy to know that, for different values of η, energy consumption of MTP₄ is always the highest one. And the relationship between energy consumption of these algorithms is $\mathrm{E}\mathrm{U}\mathrm{C}\mathrm{P}<{\mathrm{M}\mathrm{T}\mathrm{P}}_{\mathrm{1}}<{\mathrm{M}\mathrm{T}\mathrm{P}}_{\mathrm{2}}<{\mathrm{M}\mathrm{T}\mathrm{P}}_{\mathrm{3}}<{\mathrm{M}\mathrm{T}\mathrm{P}}_{\mathrm{4}}$ . With the increasing of rounds, energy consumption of MTP also increases. But for EUCP, energy consumption of each round is stable which could effectively save energy of nodes.

As shown in Figures 9–12, the differences in energy consumption between each layer are small in EUCP. However, for MTP, with the increasing of rounds, differences in energy consumption between each layer become larger and larger.

Figure 13 shows that variances of energy consumption are small in EUCP, MTP₁, and MTP₂. While with the increasing of rounds, variance of energy consumption of MTP become larger than that of EUCP.

Figure 13

Variance of energy consumption of EUCP and MTP.

5.2. Performance of Data Collection in Outer Region

We compare the energy consumption in outer region of EUCP and CDFUD algorithm. The outer region is also divided into 4 layers, whose widths are $d_5$ , $d_6$ , $d_7$ , and $d_8$ , respectively. As shown in Figure 7, the number of subregions of each layer is equal to the number of leaf nodes in the inner region and nodes in each subregion form a cluster. The number of nodes in any subregion of layer k is defined as $n_k$ , and value of the parameters in outer region are shown in Table 2.

Table 2

Parameter values of the outer region.

Parameter	Symbol	Value	Unit
Width of layer 5	$$d_5$$	40	m
Width of layer 6	$$d_6$$	50	m
Width of layer 7	$$d_7$$	60	m
Width of layer 8	$$d_8$$	70	m
Number of nodes in each cluster of layer 5	$$n_5$$	5
Number of nodes in each cluster of layer 6	$$n_6$$	10
Number of nodes in each cluster of layer 7	$$n_7$$	15
Number of nodes in each cluster of layer 8	$$n_8$$	20
Number of subregions	w	16

As shown in Figure 14, $\mathrm{E}{\mathrm{L}}_i$ and ${\mathrm{C}\mathrm{L}}_i$ are defined as the energy consumption of a cluster in the ith layer of EUCP and CDFUD, respectively. For different value of η, energy consumption of EUCP is low and well-balanced while in CDFUD it is unbalanced. Specifically, energy consumption of layer 8 is 150 times larger than that of layer 5 in CDFUD.

Figure 14

Energy consumption of EUCP and CDFUD in outer region.

As shown in Figure 15, for EUCP, the differences of energy consumption between two adjacent layers are around zero. While for CDFUD, the value is about 920 times of EUCP which verifies well-balanced energy consumption of EUCP in outer region.

Figure 15

Differences of energy consumption of EUCP and CDFUD in outer region.

As shown in Figure 16, for different value of η, the total energy consumption of EUCP is always far less than CDFUD. For transmitting the same amount of data, energy consumption of EUCP is only 6% of CDFUD.

Figure 16

Total energy consumption of EUCP and CDFUD.

As shown in Table 3, energy consumption variances of EUCP are less than 2.7 with different η. On the contrary, the value of EUCP is 9296.1. Because in CDFUD, no matter how far is the node from BS, the cluster head will directly transmit data to base station without data fusion, this will inevitably generate mass of redundant data and increase the energy consumption on sending and receiving.

Table 3

Variances of energy consumption.

Algorithm	η	Variance
EUCP	$$\eta =\mathrm{0.25}$$	1.2
	$$\eta =\mathrm{0.5}$$	1.5
	$$\eta =\mathrm{0.75}$$	0.57
	$$\eta =1$$	2.7
CDFUD	$$\eta =1$$	9296.1

6. Conclusion

A type of energy-balanced uneven clustering protocol is proposed in this paper. Sensor network is divided into two regions and the inner is further divided into clusters with different sizes. Simulation results show that EUCP could not only prolong the network lifetime but also balance the whole network energy consumption.

In the future, the expansion of clustering in the outer region will be analyzed. And the residual energy should not be the only criterion for selecting the cluster header in our future work. Moreover, the cluster head rotation strategy also needs to be considered.