A Dynamic and Energy-Efficient Clustering Algorithm in Large-Scale Mobile Sensor Networks

Abstract

Random mobility and energy constraint are two main factors affecting system performance in mobile sensor networks, which cause many difficulties to system design. It is necessary to develop high-efficiency algorithms and protocols for mobile sensor networks to adapt to dynamic network environment and energy limitation. In this paper, a new clustering algorithm based on residual energy difference ratio is presented to improve system performance. Firstly, it is an energy-efficient algorithm. The residual energy of sensor nodes and average residual energy of system are considered in the residual energy difference ratio, which effectively avoid the nodes with low residual energy being selected as cluster heads. An energy-optimal scheme is used in cluster formation phase to minimize energy consumption. Secondly, it is a dynamic algorithm. The system dynamically clusters the sensor nodes according to the data transmission delays. It makes the whole system adapt to the random mobility of sensor nodes. The NS2 software is used to simulate the new clustering algorithm. The simulation experiments can verify the validity of the proposed theory.

1. Introduction

The appearance of wireless sensor networks (WSNs) has been significantly changing various kinds of remote sensing applications. WSNs contain hundreds or thousands of sensor nodes and these sensor nodes have the ability to communicate with either one another or directly to the remote destination node (sink) [1]. They rely on batteries and have a limited power supply. If sensor nodes use up their energy, the network will be locally or totally paralyzed, which will cause short lifetime of the system.

Research on WSNs has grown rapidly and new techniques have been developed for the data-gathering and routing protocols. Multihopping method is preferred among these techniques, in which the information is routed in a cluster level fashion. All the sensor nodes in WSNs are divided into some clusters in which cluster heads (CHs) receive, data-fuse, and forward the traffic originated by cluster members to the sink. This kind of hierarchy clustering topology is easily managed and has good scalability. The aim is to prolong the network's lifetime by minimizing the transmission power. However, many clustering protocols mainly focus on static sensor nodes or controlled mobility for hop-count reduction in data collection. Mobile sensor nodes are needed in applications where sensors are deployed on randomly moving objects for monitoring, tracking, and other purposes [2]. For example, wireless sensor devices have been attached to bikes, vehicles, and animals. Other applications involving humans as participants can be flu-virus tracking or air-quality monitoring.

In recent years, mobile sensor networks (MSNs) have received increasing attention. Real-time clustering and routing protocols for MSNs are exciting areas of research because messages in the network are delivered according to their end-to-end deadlines (packet lifetime) while sensor nodes are mobile [3]. However, MSNs are not free of certain constraints such as power, computational capacities, and memory. Multi-hop idea is also suitable for MSNs.

Generally speaking, design of clustering protocols in MSNs is a greater challenge than it in WSNs due to the following reasons. Firstly, the mobility of sensor nodes is random and the topology of MSNs changes frequently. They bring more difficulties and challenges such as lower energy efficiency, shorter lifetime, and higher data delivery delays compared with WSNs [4]. Mobility also increases frame errors and the bit error rate (BER) due to low signal-to-noise ratio (SNR) [2]. Secondly, sensor nodes are tightly constrained in terms of energy, processing, and storage capacities. Thus, they require effective resource management policies, especially efficient energy management, to increase the overall lifetime of MSNs.

From the above discussion we can conclude that there are two main factors affecting the system performance in MSNs: random mobility and energy constraint. It is necessary to develop energy-efficient clustering algorithms which can effectively utilize the constrained energy and increase the overall lifetime of MSNs. In addition, the communication protocols in MSNs need to be scalable and robust enough to endure dynamic environments so that the MSNs nodes can recognize topology changes and update communication links rapidly [5].

In this work, a new clustering algorithm based on residual energy difference ratio is presented to improve the system performance of MSNs. The residual energy of sensor nodes and average residual energy of system are considered in the CH selection phase, which effectively avoid the nodes with low residual energy being selected as CHs. An energy-optimal scheme is used in the cluster formation phase. Furthermore, the sink dynamically clusters the sensor nodes according to the data transmission delays. It makes the whole system adapt to the random mobility of MSNs. The new clustering algorithm is dynamic and energy efficient which improves the lifetime, throughput rate, and energy efficiency of MSNs.

The rest of this paper is organized as follows. Section 2 presents some related works of MSNs. Network model is described in Section 3. The delay bound and energy-optimal scheme of MSNs are introduced in Section 4. Section 5 presents a clustering algorithm based on residual energy difference ratio. Theoretical analysis about the performance of MSNs is discussed in Section 6. The simulation results are given in Section 7. Finally, the conclusions are drawn in Section 8.

2. Related Works

There are two categories for the existing data-gathering protocols: hierarchy protocols and nonhierarchy protocols [6]. The hierarchy protocols have been well accepted as an effective way to make the network more scalable and reduce the energy consumption of WSNs. Clustering algorithms are used in sensor hierarchical (tree-based) routing and topology control, where CHs receive, data-fuse, and forward the traffic originated by cluster members to the sink [7]. Many clustering and routing protocols have been proposed for data-aggregating in static WSNs such as LEACH [8], HEED [9], PEGASIS [10], APTEEN [11], HIT [12], and ACW [13].

In recent years, some research studies have been done for controlled mobility in data collection of WSNs. They separately used mobile sensors [14], mobile sinks [15], and mobile data collectors [16] to design related protocols and improve network performance of WSNs. Yang et al. surveyed mechanisms into three categories [17]: mechanisms using mobile sinks, mechanisms using mobile sensor nodes redeployment, and mechanisms using mobile relays.

However, the mobility of sensor nodes in MSNs is random and uncontrolled, which imposes many difficulties on system design. The algorithms and protocols focusing on static sensor nodes or controlled mobility cannot be directly applied to MSNs. The random mobility should be considered when designing related protocols of MSNs.

A data-rate-control scheme of MSNs was proposed in [18]. Two kinds of data rate were chosen according to the buffer size of sensor nodes and the status of channel. However, the selection of data rate is more than two kinds in MSNs because of the complex channel situation. A routing algorithm based on color theory was presented for MSNs in [1]. They considered the energy efficiency of MSNs to design routing protocols. A neighbor discovery protocol for MSNs was given in [5]. The collaboration with neighbor nodes was discussed in order to recognize topology changes of MSNs. The communication characteristics were not referred to in the above research studies. Liu et al. considered a distributed clustering algorithm which was a tree-based architecture with two layers for data gathering of MSNs in [6]. However, the distribution of the selected CHs is uneven which causes uneven energy consumption and instability of MSNs.

Considering the above disadvantages, a new clustering algorithm based on residual energy difference ratio is proposed in this paper to improve the system performance of MSNs. The CHs are selected according to the residual energy difference ratio, which guarantees that the sensor nodes with more residual energy have greater possibility to be selected as CHs. In the cluster formation phase, characteristic distance is introduced to optimize the power and balance the energy consumption. In addition, the sink dynamically clusters the sensor nodes according to the data transmission delays. It makes the whole system adapt to the dynamic network environment of MSNs. Therefore, the clustering algorithm can effectively resolve the problems brought by random mobility and energy constraint. It also improves the overall lifetime, throughput rate, and energy efficiency of MSNs.

3. Network Model

In this paper, assumptions are made as follows.

• (i)

There is only one sink in MSNs. The sink is located far away from the sensor nodes and does not have energy and communication constraint.

(ii)

Initially, each sensor node has the same energy capacity. All the sensor nodes in MSNs are mobile, homogeneous, and power limited.

The network topology is modeled as follows. $G=(V,E)$ is used to represent MSNs, where V is the set of sensor nodes and E is the set of links connecting the sensor nodes. There are M sensor nodes $v_1,v_2,\dots ,v_M$ and one sink $v_{M+1}$ in the MSNs. We also assume that there are totally δ clusters in MSNs and each cluster i has $M_i$ nodes ( ${\sum }_{i=1}^{\delta }{M}_i=M$ , $i=1,\dots ,\delta$ ).

Many research studies of MSNs referred to the mobility models in other mobile networks which had some limitations in moving directions or speeds. Considering the complexity of random mobility in MSNs, we assume that the properties of network model are as follows.

• (i)

Sensor nodes can move along any directions.

(ii)

The movement of nodes does not cause the topology to change too rapidly.

4. Delay Bound and Energy-Optimal Scheme

In this paper, we introduce an ACM scheme [19, 20] into MSNs system to choose the channel's data rates according to SNR under BER bound and average power constraint. Under the scheme, $R_{\min }$ and $R_{\max }$ are separately the minimum and the maximum date rates. The maximum link (L) delay ${\tau }_{\max }$ can be derived from [21]. Therefore, the maximum delay on a path P is

$$\begin{array}{cc}& {\tau }_{\max }^P=\sum _{L\in P}{\tau }_{\max }=m{\tau }_{\max },\end{array}$$

(1)

where m is the number of hops on path P.

Matrix A is used to express the upstream communication relativity. In this case we only consider the transmitting process from sensor nodes to sink.

$$\begin{array}{cc}& A=\left[\begin{array}{ccc}{a}_{\mathrm{11}}& \cdots & a_{\mathrm{1}M+\mathrm{1}}\\ ⋮& \ddots & ⋮\\ a_{M+\mathrm{11}}& \cdots & a_{M+\mathrm{1}M+\mathrm{1}}\end{array}\right].\end{array}$$

(2)

If $v_i$ directly transmits data to $v_j$ , $a_{ij}=1$ ; otherwise, $a_{ij}=0$ ( $i,j=0,\dots ,M+1$ ). A delay calculating algorithm (DCA) is designed to acquire the upper delay bound of MSNs. The DCA algorithm is shown in Algorithm 1.

Algorithm 1: The DCA algorithm.

$u=\mathrm{0}$   /*counting the number of sensor nodes that directly transmit data to the sink.*/

For $i=\mathrm{1}$   to  M

{   $d=\mathrm{0}$ ;  /*counting the number of link hops between $v_i$ and $v_{M+1}$ .*/

  $F(i)$ ;

  $d_{iM+\mathrm{1}}^{\max }=d·{\tau }_{\max }$ ;

 If $a_{iM+1}\in A=1$ then $u=u+1$ ;

Next }

Function $F(n)\mathrm{\hspace{0.17em}\hspace{0.17em}}\hspace{0.17em}\hspace{0.17em}\{s=n$ ;

      For $t=\mathrm{1}$   to   $M+\mathrm{1}$

       If $a_{st}\in A=1$

       then $\{d=d+\mathrm{1}$ ;

          If   $t=M+\mathrm{1}$ then return

              else   $\{F(t)$ ; return $\}\}$

      Next t;

      Return}

$d_{iM+1}^{\max }$ is the maximum delay between node $v_i$ and the sink $v_{M+1}$ ( $i=0,\dots ,M$ ). u is the number of sensor nodes that directly transmit data to the sink.

Then we discuss the energy model of MSNs. The following energy model is adopted from [8, 22]. The energy consumption per second by a node that transmits data packet d meters onward, denoted as $P_{Tx}(d)$ , is

$$\begin{array}{cc}& P_{Tx}=\left({\alpha }_{\mathrm{11}}+{\alpha }_{\mathrm{2}}{d}^n\right)R,\end{array}$$

(3)

and the power by a node that receives data packet, denoted as $P_{Rx}$ , is

$$\begin{array}{cc}& P_{Rx}={\alpha }_{\mathrm{12}}R,\end{array}$$

(4)

where R is the data rate, n is the path loss exponent, ${\alpha }_{11}$ ( ${\alpha }_{12}$ ) is the power to run the transmitter (receiver) circuitry, and ${\alpha }_2$ is the power for the transmit amplifier to achieve an acceptable SNR. The total power consumption by a relay node is

$$\begin{array}{cc}& P_{\text{Relay}}\left(d\right)=\left({\alpha }_{\mathrm{1}}+{\alpha }_{\mathrm{2}}{d}^n\right)R,\end{array}$$

(5)

where ${\alpha }_1={\alpha }_{11}+{\alpha }_{12}$ , d is the distance over which the relay node transmits data.

In WSNs, data links can be established between a transmitter node A and a receiver node B separated by distance  D. Insert $K-\mathrm{1}$ relays $A_i$ ( $i=1,\dots ,K-1$ ) between A and  B. According to [23], an optimal scheme to consume minimum power is given as follows.

Theorem 1 (see [23]).

Given D and the number of intervening relays $(K-\mathrm{1})$ , $P_{Link}(D)$ is minimized when all the hop distances are made equal to $D/K$ , the optimal number of hops $K_{Opt}$ is $[D/d_{Char}]$ , where $d_{Char}$ is called the characteristic distance and given by

$$\begin{array}{cc}& d_{Char}=\sqrt[n]{\frac{{\alpha }_{\mathrm{1}}}{{\alpha }_{\mathrm{2}}\left(n-\mathrm{1}\right)}}.\end{array}$$

(6)

Corollary 2.

$P_{Link}(D)$ is bounded as

$$\begin{array}{cc}& P_{Link}\left(D\right)\ge P_{\min }\left(D\right)={\alpha }_{\mathrm{1}}\frac{n}{n-\mathrm{1}}\frac{D}{d_{Char}}{R}_{\min },\end{array}$$

(7)

with equality if and only if D is an integral multiple of $d_{Char}$ .

Proof.

From Theorem 1, when every hop distance $d=d_{\text{Cha}{\text{r}}^{}}$ , $P_{\text{Link}}(D)$ is minimized which is denoted as $P_{\min }(D)$ . Hence, combining (3)–(6), we have

$$\begin{array}{l}{P}_{\text{Link}}\left(D\right)=P_{Tx}\left(A\right)+\sum _{i=\mathrm{1}}^{K-\mathrm{1}}{P}_{\text{Relay}}\left(A_i\right)+P_{Rx}\left(B\right)\ge P_{\min }\left(D\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}=\left({\alpha }_{\mathrm{11}}+{\alpha }_{\mathrm{2}}{d}_{\text{Cha}{\text{r}}^{}}^n\right)R_{\min }+\left(K_{\text{Opt}}-\mathrm{1}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}\hspace{1em}\times \left({\alpha }_{\mathrm{1}}+{\alpha }_{\mathrm{2}}{d}_{\text{Cha}{\text{r}}^{}}^n\right)R_{\min }+{\alpha }_{\mathrm{12}}{R}_{\min }\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}=K_{\text{Opt}}\left({\alpha }_{\mathrm{1}}+{\alpha }_{\mathrm{2}}{d}_{\text{Cha}{\text{r}}^{}}^n\right)R_{\min }\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}=\frac{D}{d_{\text{Cha}{\text{r}}^{}}}\left({\alpha }_{\mathrm{1}}+{\alpha }_{\mathrm{2}}{\left(\sqrt[n]{\frac{{\alpha }_{\mathrm{1}}}{{\alpha }_{\mathrm{2}}\left(n-\mathrm{1}\right)}}\right)}^n\right)R_{\min }\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}={\alpha }_{\mathrm{1}}\frac{n}{n-\mathrm{1}}\frac{D}{d_{\text{Cha}{\text{r}}^{}}}{R}_{\min },\end{array}$$

(8)

with equality if and only if D is an integral multiple of $d_{\text{Cha}{\text{r}}^{}}$ .

Remark 3.

When node B is the sink, its energy consumption for receiving data is not included in the total energy of WSNs [23]. Under this case, $P_{\text{Link}}(D)$ is bounded as

$$\begin{array}{cc}& P_{\text{Link}}\left(D\right)\ge P_{\min }\left(D\right)={\alpha }_{\mathrm{1}}\frac{n}{n-\mathrm{1}}\frac{D}{d_{\text{Cha}{\text{r}}^{}}}{R}_{\min }-{\alpha }_{\mathrm{12}}{R}_{\min }.\end{array}$$

(9)

Based on Theorem 1, when the per-hop distance approximately equals $d_{\text{Cha}{\text{r}}^{}}$ and the data rate R is $R_{\min }$ , $P_{\text{Link}}(D)$ can approximately be regarded as $P_{\min }(D)$ .

5. Clustering Algorithm Based on Residual Energy Difference Ratio

In the CHs election of LEACH algorithm [8], they used a threshold to be the probability of being a CH for each sensor node. The threshold is as follows:

$$\begin{array}{cc}& T\left(n\right)=\{\begin{array}{cc}\frac{k}{N-k*\left(r\mathrm{mod}N/k\right)},\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}n\in G,\hfill \\ \mathrm{0},\hfill & \text{otherwise},\hfill \end{array}\end{array}$$

(10)

where N is the number of the nodes, n  ( $n=1,\dots ,N$ ) denotes each sensor node, k is the expected number of CHs, r is the number of rounds that have passed, $k*(r\mathrm{mod}N/k)$ is the number of the nodes that have been elected as CHs after r rounds, and G is the set of sensor nodes which have not been selected as CHs yet. Firstly, each sensor node generates a random number between 0 and 1. Then according to (10), the node is selected as a CH if its random number is smaller than the threshold. The effect of energy constraint and residual energy is not considered in (10), which may cause the nodes with low residual energy to be selected as CHs. In this case, those CHs will soon use up their energy, which causes the short lifetime of network.

In order to prolong the lifetime of MSNs, a residual energy difference ratio is designed in this paper to improve (10) and we get the following threshold:

$$\begin{array}{cc}& \text{Diff}\left(n\right)=\{\begin{array}{cc}\frac{k}{N-k*\left(r\mathrm{mod}N/k\right)}\hfill & \hfill \\ \hspace{1em}*\frac{E_n-E_n^{\text{CH}}}{\left|E_{\text{total}}/N_{\text{alive}}-E_n^{\text{CH}}\right|},\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}n\in G,\hfill \\ \mathrm{0},\hfill & \text{otherwise},\hfill \end{array}\end{array}$$

(11)

where $E_n$ and $E_n^{\text{CH}}$ are, respectively, the residual energy of sensor node n and its CH, $E_{\text{total}}$ is the whole energy of the nodes, $N_{\text{alive}}$ is the number of the left alive nodes, and $E_{\text{total}}/N_{\text{alive}}$ represents the average residual energy. $E_n-E_n^{\text{CH}}$ is the difference between node n and its CH. $|E_{\text{total}}/N_{\text{alive}}-E_n^{\text{CH}}|$ is the absolute value of the difference between the average residual energy and the CH. $(E_n-E_n^{\text{CH}})/|E_{\text{total}}/N_{\text{alive}}-E_n^{\text{CH}}|$ is the residual energy difference ratio. When $E_n$ is greater than $E_n^{\text{CH}}$ and $|E_{\text{total}}/N_{\text{alive}}-E_n^{\text{CH}}|$ is smaller than $E_n-E_n^{\text{CH}}$ , it will generate a larger threshold $\text{Diff}(n)$ . It indicates that node n has more residual energy than most sensor nodes. Hence, it has more possibility to be selected as a CH. In CHs selection phase, each sensor node n generates a random number $rd(n)$ between 0 and 1. Then according to (11), the node is selected as a CH if its random number is smaller than the threshold $\text{Diff}(n)$ . Using the residual energy difference ratio can efficiently avoid the nodes with low residual energy being selected as CHs. It can also guarantee that in a cluster the nodes with more energy have greater probability to be selected as CH. Therefore, it prolongs the lifetime of MSNs.

Furthermore, Liu et al. proposed ACE-C algorithm for data gathering of MSNs [6]. The algorithm had each sensor node be a CH in turns, which could guarantee that there was at least one CH elected and the number of CHs in each round was equal. However, the distribution of the selected CHs is uneven which causes uneven energy consumption. In particular in MSNs with large sensing area, it is easy for ACE-C algorithm to cause instability and short lifetime.

Considering the above disadvantages, an improved clustering algorithm is presented in this paper. Firstly, according to (11) a CH is selected. Then the CH sends message to nodes which are $d_{\text{Cha}{\text{r}}^{}}/2$ away from it. The node that receives the message joins in this cluster and transmits data to the CH. $d_{\text{Cha}{\text{r}}^{}}$ is the characteristic distance in Theorem 1. Thus, the area of a cluster is approximately equal to $S_0=\pi d_{\text{Cha}{\text{r}}^{}}^2/4$ . We can also conclude that in every cluster the distance between common nodes and their CH varies from 0 to $d_{\text{Cha}{\text{r}}^{}}/2$ . Using the same method, the next CH is selected from the rest nodes and forms its own cluster. We assume that the sensor network area is S. Therefore, it is easy to conclude that the expected number of CHs is $\delta =S/S_0$ . After all the CHs are selected, we can derive that the distance between neighbor CHs is approximately equal to the characteristic distance $d_{\text{Cha}{\text{r}}^{}}$ . All the sensor nodes transmit data to their own CHs. Then the CH fuses and uploads the collected data to its higher level neighbor CH along upstream direction towards the sink. In this way, the data is transmitted level by level. The clustering algorithm is a tree-based architecture with multiple layers for data gathering. According to the energy-optimal scheme in Theorem 1, the energy consumption is optimal and the distribution of CHs is even. The energy consumption is also balanced.

The clustering algorithm is a dynamic process in which MSNs system dynamically clusters the sensor nodes according to the data transmission delays. From DCA algorithm in Section 4, we can get the maximum delay $d_{iM+1}^{\max }$ between node $v_i$ ( $i=0,\dots ,M$ ) and the sink $v_{M+1}$ . In every clustering period, the sink reads the delay τ of every received packet whose data source is node $v_i$ and compares it with the maximum delay $d_{iM+1}^{\max }$ . If ${\tau >d}_{iM+1}^{\max }$ , it indicates that the communication condition of this path is deteriorated because of the mobility of sensor nodes. The MSNs will run the clustering algorithm to cluster sensor nodes again so that the system can adapt to the change of the network's topology. In DCA algorithm, u is derived to count the number of sensor nodes that directly transmit data to the sink. $\delta =S/S_0$ is the expected number of CHs of MSNs.

The clustering algorithm based on residual energy difference ratio (CAREDR) is shown in Algorithm 2.

Algorithm 2: The clustering algorithm based on residual energy difference ratio (CAREDR).

Input: N: the total number of sensor nodes

   δ: the expected number of CHs

/* ${\delta }_{\text{CH}}$ : the number of CHs. $V^{\prime }$ is the set of CHs. $V^{\prime \prime }$ is the set of non-CHs. $V^{\prime }\cup V^{\prime \prime }=V$ .*/

  ${\delta }_{\text{CH}}=0$ ;

For ( $i=1$ ; $i<=M$ ; $i++$ )

{If node $i\notin V^{\prime \prime }$ then continue;

 For node $i\in V^{\prime \prime }$ , according to (11) judge the value of

  $\text{Diff\hspace{0.17em}}\left(i\right)$ with the random number $rd(i)$ of node i;

 If $rd\left(i\right)<\text{Diff\hspace{0.17em}}\left(i\right)$ then $\{i\in V^{\prime }$ ; ${\delta }_{\text{CH}}={\delta }_{\text{CH}}+1$ ; Form its cluster and remove all the

          nodes in this cluster from $V^{\prime \prime }\}$ ;

 If ${\delta }_{\text{CH}}=\delta$ then break

}

End

6. Theoretical Analysis of Power and Lifetime in MSNs

Random mobility and energy constraint are two main factors affecting system performance in MSNs, which cause many difficulties on system designing. In order to improve the lifetime and energy efficiency, this paper proposes a new clustering algorithm based on residual energy difference ratio. Now theoretical analysis about power and lifetime of MSNs is given as the following theorems.

Theorem 4.

Considering cluster i with $M_i$ sensor nodes and data packet transmission rate R, the average power of such a cluster is

$$\begin{array}{cc}& E\left[P_{Cluster}\right]=\frac{\mathrm{1}}{\mathrm{2}}\left(M_i-\mathrm{1}\right)\left[{\alpha }_{\mathrm{1}}+{\alpha }_{\mathrm{2}}\frac{{\left(d_{Char}/\mathrm{2}\right)}^n}{n+\mathrm{1}}\right]\left(R_{\min }+R_{\max }\right).\end{array}$$

(12)

Proof.

According to (3)-(4), the power of such a cluster is

$$\begin{array}{cc}& P_{\text{Cluster}}=\sum _{j=\mathrm{1}}^{M_i-\mathrm{1}}\left({\alpha }_{\mathrm{11}}+{\alpha }_{\mathrm{2}}{x}^n+{\alpha }_{\mathrm{12}}\right)R.\end{array}$$

(13)

In (13), x is a random variable denoting the distance between a regular node and its CH and R is the random variable denoting data rate. Two-dimensional random variable $(X,R)$ follows uniform distribution over the areas $\mathrm{0}\le x\le d_{\text{Cha}{\text{r}}^{}}/2$ and $R_{\min }\le R\le R_{\max }$ . We have the average power of a cluster as follows:

$$\begin{array}{l}E\left[P_{\text{Cluster}}\right]={\int }_{-\infty }^{+\infty }{\int }_{-\infty }^{+\infty }{P}_{\text{Cluster}}f\left(x,r\right)dx\hspace{0.17em}dr\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}={\int }_{\mathrm{0}}^{d_{\text{Cha}{\text{r}}^{}}/\mathrm{2}}{\int }_{R_{\min }}^{R_{\max }}\sum _{j=\mathrm{1}}^{M_i-\mathrm{1}}\left({\alpha }_{\mathrm{1}}+{\alpha }_{\mathrm{2}}{x}^n\right)R\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\times \frac{\mathrm{1}}{\left(d_{\text{Cha}{\text{r}}^{}}/\mathrm{2}\right)\left(R_{\max }-R_{\min }\right)}dx\hspace{0.17em}dr\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}=\left(M_i-\mathrm{1}\right)\left[{\alpha }_{\mathrm{1}}+{\alpha }_{\mathrm{2}}\frac{{\left(d_{\text{Cha}{\text{r}}^{}}/\mathrm{2}\right)}^n}{n+\mathrm{1}}\right]\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\times {\int }_{R_{\min }}^{R_{\max }}\frac{R}{\left(R_{\max }-R_{\min }\right)}dr\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}=\frac{\mathrm{1}}{\mathrm{2}}\left(M_i-\mathrm{1}\right)\left[{\alpha }_{\mathrm{1}}+{\alpha }_{\mathrm{2}}\frac{{\left(d_{\text{Cha}{\text{r}}^{}}/\mathrm{2}\right)}^n}{n+\mathrm{1}}\right]\left({R_{\min }+R}_{\max }\right).\end{array}$$

(14)

Corollary 5.

Considering cluster i with $M_i$ sensor nodes and data packet transmission rate R, the average minimum power of such a cluster is

$$\begin{array}{cc}& E\left[P_{Cluster}^{\min }\right]=\left(M_i-\mathrm{1}\right)\left[{\alpha }_{\mathrm{1}}+{\alpha }_{\mathrm{2}}\frac{{\left(d_{Char}/\mathrm{2}\right)}^n}{n+\mathrm{1}}\right]R_{\min }.\end{array}$$

(15)

Proof.

According to (3)-(4), the minimum power of such a cluster is

$$\begin{array}{cc}& P_{\text{Cluster}}^{\min }=\sum _{j=\mathrm{1}}^{M_i-\mathrm{1}}\left({\alpha }_{\mathrm{11}}+{\alpha }_{\mathrm{2}}{x}^n+{\alpha }_{\mathrm{12}}\right)R_{\min }.\end{array}$$

(16)

In (16), x is the random variable denoting the distance between a regular node and its CH and $R=R_{\min }$ is the minimum data rate. Random variable X follows uniform distribution over the area $\mathrm{0}\le x\le d_{\text{Cha}{\text{r}}^{}}/2$ . We have the average minimum power of a cluster as follows:

$$\begin{array}{l}\mathrm{\hspace{0.17em}\hspace{0.17em}}E\left[P_{\text{Cluster}}^{\min }\right]={\int }_{-\infty }^{+\infty }{P}_{\text{Cluster}}^{\min }f\left(x\right)dx\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}\hspace{0.17em}={\int }_{\mathrm{0}}^{d_{\text{Cha}{\text{r}}^{}}/\mathrm{2}}\sum _{j=\mathrm{1}}^{M_i-\mathrm{1}}\left({\alpha }_{\mathrm{1}}+{\alpha }_{\mathrm{2}}{x}^n\right)R_{\min }\times \frac{\mathrm{1}}{d_{\text{Cha}{\text{r}}^{}}/\mathrm{2}}dx\\ =\left(M_i-\mathrm{1}\right)\left[{\alpha }_{\mathrm{1}}+{\alpha }_{\mathrm{2}}\frac{{\left(d_{\text{Cha}{\text{r}}^{}}/\mathrm{2}\right)}^n}{n+\mathrm{1}}\right]R_{\min }.\end{array}$$

(17)

Theorem 6.

Considering MSNs with M sensor nodes, the lifetime of MSNs is bounded as

$$\begin{array}{cc}& \ell \le {\ell }_{\max }=\frac{M{E}_{\mathrm{0}}}{{\mathrm{\Psi }R}_{\min }},\end{array}$$

(18)

where $\mathrm{\Psi }=(M+\delta /(n-\mathrm{1})){\alpha }_{\mathrm{1}}+(M-\delta )({(d_{Char}/\mathrm{2})}^n/(n+\mathrm{1})){\alpha }_{\mathrm{2}}-u{\alpha }_{\mathrm{12}}$ .

Proof.

Clearly, the total energy consumed in MSNs is not greater than the total energy available in the beginning, that is,

$$\begin{array}{cc}& \ell ·P_{\text{MSNs}}\le \sum _{i=\mathrm{1}}^M{e}_i\left(\mathrm{0}\right),\end{array}$$

(19)

where $e_i(0)$ is the initial energy of sensor node i and $P_{\text{MSNs}}$ is the energy consumption per second by MSNs which is composed of two parts: the energy consumption per second by all clusters and the energy consumption per second by all links. From the discussions above, there are totally δ clusters in MSNs and each cluster i has $M_i$ nodes ( ${\sum }_{i=1}^{\delta }{M}_i=M$ , $i=1,\dots ,\delta$ ). Among δ clusters there are u CHs that directly transmit data to the sink and $\delta -u$ CHs that transmit data to their higher level neighbor CHs. u can be derived from DCA algorithm in Section 4. We can also conclude that there are u links on which CHs directly transmit data to the sink, so their energy consumption for receiving data is not included in the total energy of MSNs. Furthermore, our clustering algorithm makes the transmitting distance of all links approximately equal to $d_{\text{Cha}{\text{r}}^{}}$ . In this paper, we assume that the initial energy of all the sensor nodes is the same, that is, $e_i(0)=E_0$ ( $i=1,\dots ,M$ ). From (19), we have

$$\begin{array}{l}\ell \le \frac{M{E}_{\mathrm{0}}}{P_{\text{MSNs}}}\le {\ell }_{\max }\\ \hspace{0.17em}\hspace{0.17em}=\frac{M{E}_{\mathrm{0}}}{{\sum }_{i=\mathrm{1}}^{\delta }{P}_{\text{Cluster}}^{\min }\left(i\right)+{\sum }_{j=\mathrm{1}}^u{P}_{\text{Link}}\left(L_j\right)+{\sum }_{m=\mathrm{1}}^{\delta -u}{P}_{\text{Link}}\left(L_m\right)}.\end{array}$$

(20)

From (7), (9), and (15), we conclude

$$\begin{array}{l}\ell \le {\ell }_{\max }\\ \hspace{0.17em}\hspace{0.17em}=\left(M{E}_{\mathrm{0}}\right)\times (\sum _{i=\mathrm{1}}^{\delta }\left(M_i-\mathrm{1}\right)\left[{\alpha }_{\mathrm{1}}+{\alpha }_{\mathrm{2}}\frac{{\left(d_{\text{Cha}{\text{r}}^{}}/\mathrm{2}\right)}^n}{n+\mathrm{1}}\right]R_{\min }\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+u\left({\alpha }_{\mathrm{1}}\frac{n}{n-\mathrm{1}}-{\alpha }_{\mathrm{12}}\right)R_{\min }\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+{\left(\delta -u\right){\alpha }_{\mathrm{1}}\frac{n}{n-\mathrm{1}}{R}_{\min }\phantom{\sum _{i=\mathrm{1}}^{\delta }\left(M_i-\mathrm{1}\right)\left[{\alpha }_{\mathrm{1}}+{\alpha }_{\mathrm{2}}\frac{{\left(d_{\mathrm{0000}}/\mathrm{2}\right)}^n}{n+\mathrm{1}}\right]R_{\min }})}^{-1}\\ \hspace{0.17em}\hspace{0.17em}=\left(M{E}_{\mathrm{0}}\right)\times (\left(M-\delta \right)\left[{\alpha }_{\mathrm{1}}+{\alpha }_{\mathrm{2}}\frac{{\left(d_{\text{Cha}{\text{r}}^{}}/\mathrm{2}\right)}^n}{n+\mathrm{1}}\right]R_{\min }\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}+{\delta {\alpha }_{\mathrm{1}}\frac{n}{n-\mathrm{1}}{R}_{\min }-u{\alpha }_{\mathrm{12}}{R}_{\min }\phantom{\left[{\alpha }_{\mathrm{1}}+{\alpha }_{\mathrm{2}}\frac{{\left(d_{\mathrm{0000}}/\mathrm{2}\right)}^n}{n+\mathrm{1}}\right]})}^{-1}\\ \hspace{0.17em}\hspace{0.17em}=\left(M{E}_{\mathrm{0}}\right)\times ([\phantom{\left({\left(d_{\text{0000}}/\mathrm{2}\right)}^n/\left(n+\mathrm{1}\right)\right)}\left(M+\frac{\delta }{n-\mathrm{1}}\right){\alpha }_{\mathrm{1}}+\left(M-\delta \right)\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\hspace{1em}\times {\left(\frac{{\left(d_{\text{Cha}{\text{r}}^{}}/\mathrm{2}\right)}^n}{n+\mathrm{1}}\right){\alpha }_{\mathrm{2}}-u{\alpha }_{\mathrm{12}}]R_{\min })}^{-1}\\ \hspace{0.17em}\hspace{0.17em}=\frac{M{E}_{\mathrm{0}}}{{\mathrm{\Psi }R}_{\min }}.\end{array}$$

(21)

Then we have

$$\begin{array}{cc}& \ell \le {\ell }_{\max }=\frac{M{E}_{\mathrm{0}}}{{\mathrm{\Psi }R}_{\min }},\end{array}$$

(22)

where $\mathrm{\Psi }=(M+\delta /(n-\mathrm{1})){\alpha }_{\mathrm{1}}+(M-\delta )({(d_{\text{Cha}{\text{r}}^{}}/\mathrm{2})}^n/(n+\mathrm{1})){\alpha }_{\mathrm{2}}-u{\alpha }_{\mathrm{12}}$ .

7. Simulations

In this paper, we use NS2 simulation tools [24–26] to simulate the clustering algorithm CAREDR. The simulation environment is set up as follows. The sensor network area considered in the simulation is 500 m × 500 m. There are 500 sensor nodes and one sink. The simulation parameters are shown in Table 1.

Table 1

Parameters used in the simulation.

Items	Values
Network area	$\mathrm{500}\hspace{0.17em}\text{m}\times \mathrm{500}\hspace{0.17em}\text{m}$
Initial energy	2 J
Simulation time	500 s
Sink location	(50, 75)
${\alpha }_1,{\alpha }_2$	$\mathrm{100}e-9$  J/bit/m2, $\mathrm{9.68}e-\mathrm{12}$  J/bit/m2

In this experiment, the throughput, energy consumption, and lifetime of the network are simulated. From (6) in Theorem 1, we can get $d_{\text{Cha}{\text{r}}^{}}=101$ . The expected number of cluster heads δ can be calculated from the relative formula in Section 5: $\delta =31$ . The average power and its lower bound of each cluster are discussed in Section 6 which can help to calculate $\text{Diff}(n)$ and select suitable CHs. The upper bound of lifetime in Theorem 6 can offer theoretical reference of system performance comparison.

We compare the results obtained by CAREDR with those of using LEACH and ACE-C under the same circumstances. As shown in Figure 1, the throughput of CAREDR is higher than LEACH and ACE-C. It is approximately increased by 49.06% and 300.32%, respectively. Figure 2 shows that the new algorithm has lower energy consumption than LEACH and ACE-C, which is approximately decreased by 7.92% and 11.94%, respectively. Figure 3 shows the death rate of the nodes through which we can conclude that the new algorithm has longer lifetime than LEACH and ACE-C. The lifetime is approximately increased by 5.82% and 13.18%, respectively. Our CAREDR algorithm effectively improves the performance of MSNs.

Figure 1

Comparison of the throughput.

Figure 2

Comparison of the energy consumption.

Figure 3

Comparison of the lifetime.

8. Conclusions

In order to improve the performance of MSNs, a new clustering algorithm based on residual energy difference ratio is presented in this paper.

It is a dynamic and energy-efficient algorithm which improves the lifetime, throughput rate, and energy efficiency of MSNs. The residual energy of sensor nodes and average residual energy of system are considered in the CHs selection phase, which effectively avoid the nodes with low residual energy being selected as CHs. An energy-optimal scheme is used in the cluster formation phase. Furthermore, the sink dynamically clusters the sensor nodes according to the data transmission delays. It makes the whole system adapt to the random mobility of MSNs.