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}^{δ} M_{i} = M$ , $i = 1, \dots, δ$ ).

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 $τ_{\max}$ can be derived from [21]. Therefore, the maximum delay on a path P is

\begin{matrix} τ_{\max}^{P} = \sum_{L \in P} τ_{\max} = m τ_{\max}, \end{matrix}

(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{matrix} A = [\begin{bmatrix} a_{11} & \dots & a_{1 M + 1} \\ ⋮ & ⋱ & ⋮ \\ a_{M + 11} & \dots & a_{M + 1 M + 1} \end{bmatrix}] . \end{matrix}

(2)

If $v_{i}$ directly transmits data to $v_{j}$ , $a_{i j} = 1$ ; otherwise, $a_{i j} = 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 = 0$ /*counting the number of sensor nodes that directly transmit data to the sink.*/

For $i = 1$ to M

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

$F (i)$ ;

$d_{i M + 1}^{\max} = d \cdot τ_{\max}$ ;

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

Next }

Function $F (n) {s = n$ ;

For $t = 1$ to $M + 1$

If $a_{s t} \in A = 1$

then ${d = d + 1$ ;

If $t = M + 1$ then return

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

Next t;

Return}

$d_{i M + 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_{T x} (d)$ , is

\begin{matrix} P_{T x} = (α_{11} + α_{2} d^{n}) R, \end{matrix}

(3)

and the power by a node that receives data packet, denoted as

P_{R x}

, is

\begin{matrix} P_{R x} = α_{12} R, \end{matrix}

(4)

where R is the data rate, n is the path loss exponent,

α_{11}

(

α_{12}

) is the power to run the transmitter (receiver) circuitry, and

α_{2}

is the power for the transmit amplifier to achieve an acceptable SNR. The total power consumption by a relay node is

\begin{matrix} P_{Relay} (d) = (α_{1} + α_{2} d^{n}) R, \end{matrix}

(5)

where

α_{1} = α_{11} + α_{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 - 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 - 1)$ , $P_{L i n k} (D)$ is minimized when all the hop distances are made equal to $D / K$ , the optimal number of hops $K_{O p t}$ is $[D / d_{C h a r}]$ , where $d_{C h a r}$ is called the characteristic distance and given by

\begin{matrix} d_{C h a r} = \sqrt[n]{\frac{α_{1}}{α_{2} (n - 1)}} . \end{matrix}

(6)

Corollary 2.

$P_{L i n k} (D)$ is bounded as

\begin{matrix} P_{L i n k} (D) \geq P_{\min} (D) = α_{1} \frac{n}{n - 1} \frac{D}{d_{C h a r}} R_{\min}, \end{matrix}

(7)

with equality if and only if D is an integral multiple of

d_{C h a r}

Proof.

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

\begin{array}{l} P_{Link} (D) = P_{T x} (A) + \sum_{i = 1}^{K - 1} P_{Relay} (A_{i}) + P_{R x} (B) \geq P_{\min} (D) \\ = (α_{11} + α_{2} d_{Cha r^{}}^{n}) R_{\min} + (K_{Opt} - 1) \\ \times (α_{1} + α_{2} d_{Cha r^{}}^{n}) R_{\min} + α_{12} R_{\min} \\ = K_{Opt} (α_{1} + α_{2} d_{Cha r^{}}^{n}) R_{\min} \\ = \frac{D}{d_{Cha r^{}}} (α_{1} + α_{2} {(\sqrt[n]{\frac{α_{1}}{α_{2} (n - 1)}})}^{n}) R_{\min} \\ = α_{1} \frac{n}{n - 1} \frac{D}{d_{Cha r^{}}} R_{\min}, \end{array}

(8)

with equality if and only if D is an integral multiple of

d_{Cha 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_{Link} (D)$ is bounded as

\begin{matrix} P_{Link} (D) \geq P_{\min} (D) = α_{1} \frac{n}{n - 1} \frac{D}{d_{Cha r^{}}} R_{\min} - α_{12} R_{\min} . \end{matrix}

(9)

Based on Theorem 1, when the per-hop distance approximately equals $d_{Cha r^{}}$ and the data rate R is $R_{\min}$ , $P_{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{matrix} T (n) = {\begin{cases} \frac{k}{N - k * (r \mod N / k)}, & if n \in G, \\ 0, & otherwise, \end{cases} \end{matrix}

(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 \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{matrix} Diff (n) = {\begin{cases} \frac{k}{N - k * (r \mod N / k)} \\ * \frac{E_{n} - E_{n}^{CH}}{| E_{total} / N_{alive} - E_{n}^{CH} |}, & if n \in G, \\ 0, & otherwise, \end{cases} \end{matrix}

(11)

where

E_{n}

and

E_{n}^{CH}

are, respectively, the residual energy of sensor node n and its CH,

E_{total}

is the whole energy of the nodes,

N_{alive}

is the number of the left alive nodes, and

E_{total} / N_{alive}

represents the average residual energy.

E_{n} - E_{n}^{CH}

is the difference between node n and its CH.

| E_{total} / N_{alive} - E_{n}^{CH} |

is the absolute value of the difference between the average residual energy and the CH.

(E_{n} - E_{n}^{CH}) / | E_{total} / N_{alive} - E_{n}^{CH} |

is the residual energy difference ratio. When

E_{n}

is greater than

E_{n}^{CH}

and

| E_{total} / N_{alive} - E_{n}^{CH} |

is smaller than

E_{n} - E_{n}^{CH}

, it will generate a larger threshold

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

r d (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

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_{Cha r^{}} / 2$ away from it. The node that receives the message joins in this cluster and transmits data to the CH. $d_{Cha r^{}}$ is the characteristic distance in Theorem 1. Thus, the area of a cluster is approximately equal to $S_{0} = π d_{Cha r^{}}^{2} / 4$ . We can also conclude that in every cluster the distance between common nodes and their CH varies from 0 to $d_{Cha 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 $δ = 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_{Cha 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_{i M + 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_{i M + 1}^{\max}$ . If ${τ > d}_{i M + 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. $δ = 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

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

$δ_{CH} = 0$ ;

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

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

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

$Diff (i)$ with the random number $r d (i)$ of node i;

If $r d (i) < Diff (i)$ then ${i \in V^{'}$ ; $δ_{CH} = δ_{CH} + 1$ ; Form its cluster and remove all the

nodes in this cluster from $V^{''}}$ ;

If $δ_{CH} = δ$ 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{matrix} E [P_{C l u s t e r}] = \frac{1}{2} (M_{i} - 1) [ α_{1} + α_{2} \frac{{(d_{C h a r} / 2)}^{n}}{n + 1} ] (R_{\min}  +  R_{\max}) . \end{matrix}

(12)

Proof.

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

\begin{matrix} P_{Cluster} = \sum_{j = 1}^{M_{i} - 1} (α_{11} + α_{2} x^{n} + α_{12}) R . \end{matrix}

(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 $0 \leq x \leq d_{Cha r^{}} / 2$ and $R_{\min} \leq R \leq R_{\max}$ . We have the average power of a cluster as follows:

\begin{array}{l} E [P_{Cluster}] = \int_{- \infty}^{+ \infty} \int_{- \infty}^{+ \infty} P_{Cluster} f (x, r) d x d r \\ = \int_{0}^{d_{Cha r^{}} / 2} \int_{R_{\min}}^{R_{\max}} \sum_{j = 1}^{M_{i} - 1} (α_{1} + α_{2} x^{n}) R \\ \times \frac{1}{(d_{Cha r^{}} / 2) (R_{\max} - R_{\min})} d x d r \\ = (M_{i} - 1) [α_{1} + α_{2} \frac{{(d_{Cha r^{}} / 2)}^{n}}{n + 1}] \\ \times \int_{R_{\min}}^{R_{\max}} \frac{R}{(R_{\max} - R_{\min})} d r \\ = \frac{1}{2} (M_{i} - 1) [α_{1} + α_{2} \frac{{(d_{Cha r^{}} / 2)}^{n}}{n + 1}] ({R_{\min}  +  R}_{\max}) . \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{matrix} E [P_{C l u s t e r}^{\min}] = (M_{i} - 1) [α_{1} + α_{2} \frac{{(d_{C h a r} / 2)}^{n}}{n + 1}] R_{\min} . \end{matrix}

(15)

Proof.

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

\begin{matrix} P_{Cluster}^{\min} = \sum_{j = 1}^{M_{i} - 1} (α_{11} + α_{2} x^{n} + α_{12}) R_{\min} . \end{matrix}

(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 $0 \leq x \leq d_{Cha r^{}} / 2$ . We have the average minimum power of a cluster as follows:

\begin{array}{l} E [P_{Cluster}^{\min}] = \int_{- \infty}^{+ \infty} P_{Cluster}^{\min} f (x) d x \\ = \int_{0}^{d_{Cha r^{}} / 2} \sum_{j = 1}^{M_{i} - 1} (α_{1} + α_{2} x^{n}) R_{\min} \times \frac{1}{d_{Cha r^{}} / 2} d x \\ = (M_{i} - 1) [α_{1} + α_{2} \frac{{(d_{Cha r^{}} / 2)}^{n}}{n + 1}] R_{\min} . \end{array}

(17)

Theorem 6.

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

\begin{matrix} ℓ \leq ℓ_{\max} = \frac{M E_{0}}{{Ψ R}_{\min}}, \end{matrix}

(18)

where

Ψ = (M + δ / (n - 1)) α_{1} + (M - δ) ({(d_{C h a r} / 2)}^{n} / (n + 1)) α_{2} - u α_{12}

Proof.

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

\begin{matrix} ℓ \cdot P_{MSNs} \leq \sum_{i = 1}^{M} e_{i} (0), \end{matrix}

(19)

where

e_{i} (0)

is the initial energy of sensor node i and

P_{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}^{δ} M_{i} = M

i = 1, \dots, δ

). Among δ clusters there are u CHs that directly transmit data to the sink and

δ - 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_{Cha 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} ℓ \leq \frac{M E_{0}}{P_{MSNs}} \leq ℓ_{\max} \\ = \frac{M E_{0}}{\sum_{i = 1}^{δ} P_{Cluster}^{\min} (i) + \sum_{j = 1}^{u} P_{Link} (L_{j}) + \sum_{m = 1}^{δ - u} P_{Link} (L_{m})} . \end{array}

(20)

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

\begin{array}{l} ℓ \leq ℓ_{\max} \\ = (M E_{0}) \times (\sum_{i = 1}^{δ} (M_{i} - 1) [α_{1} + α_{2} \frac{{(d_{Cha r^{}} / 2)}^{n}}{n + 1}] R_{\min} \\ + u (α_{1} \frac{n}{n - 1} - α_{12}) R_{\min} \\ + {(δ - u) α_{1} \frac{n}{n - 1} R_{\min})}^{- 1} \\ = (M E_{0}) \times ((M - δ) [α_{1} + α_{2} \frac{{(d_{Cha r^{}} / 2)}^{n}}{n + 1}] R_{\min} \\ + {δ α_{1} \frac{n}{n - 1} R_{\min} - u α_{12} R_{\min})}^{- 1} \\ = (M E_{0}) \times ([(M + \frac{δ}{n - 1}) α_{1} + (M - δ) \\ \times {(\frac{{(d_{Cha r^{}} / 2)}^{n}}{n + 1}) α_{2} - u α_{12}] R_{\min})}^{- 1} \\ = \frac{M E_{0}}{{Ψ R}_{\min}} . \end{array}

(21)

Then we have

\begin{matrix} ℓ \leq ℓ_{\max} = \frac{M E_{0}}{{Ψ R}_{\min}}, \end{matrix}

(22)

where

Ψ = (M + δ / (n - 1)) α_{1} + (M - δ) ({(d_{Cha r^{}} / 2)}^{n} / (n + 1)) α_{2} - u α_{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	$500 m \times 500 m$
Initial energy	2 J
Simulation time	500 s
Sink location	(50, 75)
$α_{1}, α_{2}$	$100 e - 9$ J/bit/m², $9.68 e - 12$ J/bit/m²

In this experiment, the throughput, energy consumption, and lifetime of the network are simulated. From (6) in Theorem 1, we can get $d_{Cha r^{}} = 101$ . The expected number of cluster heads δ can be calculated from the relative formula in Section 5: $δ = 31$ . The average power and its lower bound of each cluster are discussed in Section 6 which can help to calculate $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.

Footnotes

Acknowledgment

This work is supported by NSFC under Grant no. 61202470.

References

Chang

T.-J.

Wang

Hsieh

Y.-L.

A color-theory-based energy efficient routing algorithm for mobile wireless sensor networks

Computer Networks 2008 52 3 531 541

2-s2.0-38549161190

10.1016/j.comnet.2007.10.004

Ngo

Anpalagan

A detailed review of energy-efficient medium access control protocols for mobile sensor networks

Computers and Electrical Engineering 2010 36 2 383 396

2-s2.0-75949124643

10.1016/j.compeleceng.2009.03.005

Ahmed

A. A.

An enhanced real-time routing protocol with load distribution for mobile wireless sensor networks

Computer Networks 2013 57 1459 1473

Hwang

Talipov

Cha

Distributed geographic service discovery for mobile sensor networks

Computer Networks 2011 55 5 1069 1082

2-s2.0-79952440636

10.1016/j.comnet.2010.09.015

Kohvakka

Suhonen

Kuorilehto

Kaseva

Hännikäinen

Hämäläinen

T. D.

Energy-efficient neighbor discovery protocol for mobile wireless sensor networks

Ad Hoc Networks 2009 7 1 24 41

2-s2.0-53549120933

10.1016/j.adhoc.2007.11.016

Liu

C.-M.

Lee

C.-H.

Wang

L.-C.

Distributed clustering algorithms for data-gathering in wireless mobile sensor networks

Journal of Parallel and Distributed Computing 2007 67 11 1187 1200

2-s2.0-34548832220

10.1016/j.jpdc.2007.06.010

Guizani

Sharif

Adaptive clustering in wireless sensor networks by mining sensor energy data

Computer Communications 2007 30 14-15 2968 2975

2-s2.0-34548840533

10.1016/j.comcom.2007.05.027

Heinzelman

W. B.

Chandrakasan

A. P.

Balakrishnan

An application-specific protocol architecture for wireless microsensor networks

IEEE Transactions on Wireless Communications 2002 1 4 660 670

2-s2.0-33646589837

10.1109/TWC.2002.804190

Younis

Fahmy

HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks

IEEE Transactions on Mobile Computing 2004 3 4 366 379

2-s2.0-10944266504

10.1109/TMC.2004.41

10.

Lindsey

Raghavendra

Sivalingam

K. M.

Data gathering algorithms in sensor networks using energy metrics

IEEE Transactions on Parallel and Distributed Systems 2002 13 9 924 935

2-s2.0-0036766616

10.1109/TPDS.2002.1036066

11.

Manjeshwar

Agrawal

D. P.

APTEEN: a hybrid protocol for efficient routing and comprehensive information retrieval in wireless sensor networks

Proceedings of the 16th International Parallel and Distributed Proceedings Symposium (IPDPS ’02)

April 2002

195 202

12.

Culpepper

B. J.

Dung

Moh

Design and analysis of hybrid indirect transmissions (HIT) for data gathering in wireless micro sensor networks

ACM SIGMOBILE Mobile Computing and Communications Review 2004 8 1 61 83

13.

Tian

Georganas

N. D.

A node scheduling scheme for energy conservation in large wireless sensor networks

Wireless Communications and Mobile Computing 2003 3 2 271 290

2-s2.0-3042738623

10.1002/wcm.116

14.

Ballari

de Bruin

Bregt

A. K.

Value of information and mobility constraints for sampling with mobile sensors

Computers & Geosciences 2012 49 102 111

15.

Rao

Biswas

Analyzing multi-hop routing feasibility for sensor data harvesting using mobile sinks

Journal of Parallel and Distributed Computing 2012 72 6 764 777

2-s2.0-84859915521

10.1016/j.jpdc.2012.02.017

16.

Vupputuri

Rachuri

K. K.

Siva Ram Murthy

Using mobile data collectors to improve network lifetime of wireless sensor networks with reliability constraints

Journal of Parallel and Distributed Computing 2010 70 7 767 778

2-s2.0-77955418699

10.1016/j.jpdc.2010.03.010

17.

Yang

Fonoage

M. I.

Cardei

Improving network lifetime with mobile wireless sensor networks

Computer Communications 2010 33 4 409 419

2-s2.0-74149091307

10.1016/j.comcom.2009.11.010

18.

Shimamoto

A cognitive mobile sensor network for environment observation

Telematics and Informatics 2012 29 1 26 32

2-s2.0-80052795642

10.1016/j.tele.2011.03.001

19.

Goldsmith

A. J.

Chua

S. G.

Variable-rate variable-power MQAM for fading channels

IEEE Transactions on Communications 1997 45 10 1218 1230

2-s2.0-0031257246

10.1109/26.634685

20.

Hole

K. J.

Holm

Øien

G. E.

Adaptive multidimensional coded modulation over flat fading channels

IEEE Journal on Selected Areas in Communications 2000 18 7 1153 1158

2-s2.0-0034227089

10.1109/49.857915

21.

Yang

Guan

X.-P.

Long

C.-N.

Luo

X.-Y.

Analysis and design of wireless networked control system utilizing adaptive coded modulation

Acta Automatica Sinica 2009 35 7 911 918

2-s2.0-68049098103

10.3724/SP.J.1004.2009.00911

22.

Jin

Wang

Kim

Yang

EEMC: an energy-efficient multi-level clustering algorithm for large-scale wireless sensor networks

Computer Networks 2008 52 3 542 562

2-s2.0-38549179940

10.1016/j.comnet.2007.10.005

23.

Bhardwaj

Garnett

Chandrakasan

A. P.

Upper bounds on the lifetime of sensor networks

Proceedings of the IEEE International Conference on Communications

June 2001

785 790

2-s2.0-0034865944

24.

Cheng

Deng

NS2 Simulation Experiment 2008

Beijing, China

Electronic Industry Press

25.

Sun

Wen

NS2 and Network Simulation 2007

Beijing, China

The People's Posts and Telecommunications Press

26.

Fang

Liu

Chen

Basis and Applications of NS-2 Network Simulation 2008

Beijing, China

National Defense Industry Press