Sage Journals: Discover world-class research

Abstract

Due to the imbalance of energy consumption of nodes in wireless sensor networks (WSNs), some local nodes die prematurely, which causes the network partitions and then shortens the lifetime of the network. The phenomenon is called “hot spot” or “energy hole” problem. For this problem, an energy-aware distributed unequal clustering protocol (EADUC) in multihop heterogeneous WSNs is proposed. Compared with the previous protocols, the cluster heads obtained by EADUC can achieve balanced energy, good distribution, and seamless coverage for all the nodes. Moreover, the complexity of time and control message is low. Simulation experiments show that EADUC can prolong the lifetime of the network significantly.

1. Introduction

A wireless sensor network (WSN) consists of thousands of low-cost, low-power, and tiny sensor nodes which can be widely used in military, national security, environmental science, traffic management, disaster prediction, medical, manufacturing industry, and city information construction. As sensor networks have limited and nonrechargeable energy resources, energy efficiency is a very important issue in designing the topology, which affects the lifetime of sensor networks greatly.

Clustering is proved to be an effective scheme in increasing the scalability and lifetime of WSNs. In clustering schemes, sensor nodes are grouped into clusters and a main node is selected as the cluster head (CH) of a cluster and the other nodes are called cluster members (CMs) [1]. Each CM collects local data from the environment periodically and then sends it to the CH. When the data from all the CMs arrives, the CHs aggregate the data and send it to the BS.

As CHs are responsible for receiving and aggregating the data from their CMs, and transmitting the aggregated data to a long distance, The energy consumption of CHs is much larger than that of CMs. In order to balance the energy among nodes, most clustering algorithms divide the operation into rounds and periodically rotate the roles of CHs in the network. However, there is one more question. Energy consumption among cluster heads is imbalanced due to the distance to the BS. In single-hop networks, CHs farther away from the BS need to transmit data to a long distance. Therefore, the energy of CHs farther away from the BS is larger than that of the CHs closer to the BS. In multihop networks, CHs closer to the BS undertake data forwarding, which means that the energy consumption of CHs closer to the BS is larger. The imbalanced energy consumption of nodes leads to a certain number of nodes dying prematurely, causing network partitions. This phenomenon is called “hot spot” problem or “energy hole” problem [2]. Researchers proved that unequal clustering algorithms can effectively mitigate the “energy hole” problem.

In this paper, an energy-aware distributed unequal clustering protocol in multihop heterogeneous wireless sensor networks is proposed. It elects cluster heads based on the ratio between the average residual energy of neighbor nodes and the residual energy of the node itself, and uses uneven competition ranges to construct clusters of uneven sizes. The cluster heads closer to the BS have smaller cluster sizes to preserve some energy for the intercluster data forwarding, which can balance the energy consumption among cluster heads and prolong the network lifetime.

The rest of the paper is organized as follows. Section 2 covers the related works in this area. Section 3 exhibits the network model and problem description. Section 4 presents the energy-aware distributed unequal clustering protocol in detail. Section 5 analyzes several properties of the algorithm. In Section 6 we describe our simulation efforts and the analysis of results. Finally, Section 7 concludes the paper.

2. Related Work

LEACH [3] is a typical clustering protocol proposed for periodical data gathering applications in wireless sensor networks. In LEACH, each node independently elects itself as a cluster head with a probability. Cluster heads receive and aggregate data from cluster members and send the aggregated data to the BS by single-hop communication. In order to balance the energy consumption, the role of cluster head is periodically rotated among the nodes. LEACH protocol is simple and does not require a large communication overhead. However, the performance of LEACH in heterogeneous networks is not very well, because it elects cluster heads without considering the residual energy of nodes. To solve this problem, researchers improved LEACH and proposed some new algorithms such as centralized algorithm LEACH-C [4], multi-level clustering algorithm EEMLC [5], algorithm based on heterogeneous networks EEHC [6], and algorithm based on multihop communication LEACH-M [7].

EADEEG [8] is a novel distributed clustering algorithm. It elects cluster heads based on the ratio between the average residual energy of neighbor nodes and the residual energy of the node itself, which can achieve a good cluster heads distribution and prolong the network lifetime. There are still two points needed to be improved in EADEEG. (1) In some cases, there are “isolate points” in EADEEG. (2) It chooses 2 $r_{c}$ as intercluster communication radius, which cannot ensure the connectivity among cluster heads. For these problems, a distributed energy saving clustering algorithm called BPEC is proposed in [1]. BPEC elects cluster heads by the ratio between the average residual energy of neighbor nodes and the residual energy of the node itself as its primary probability and the node's degree as its subsidiary probability. It is proved that BPEC can avoid the “isolate points” problem in EADEEG and can keep all the cluster heads connected.

In [9, 10], energy-efficient distributed clustering algorithms HEED and EEDC are proposed. They choose sensor nodes to be cluster heads iteratively.

However, none of these algorithms mentioned above takes the solution of “energy hole” problem into account. To solve this problem, Soro and Heinzelman proposed an unequal clustering algorithm in [11]. The network field is divided into cirques. Clusters in the same cirque have the same size while clusters in the different cirques have different sizes. Deploying some high-energy nodes to take on the cluster head role to control network operation ensures that energy dissipation of these cluster heads is balanced. The algorithm can effectively prolong network lifetime. However, some high-energy nodes are needed to play as cluster heads, so the positions of cluster heads must be calculated previously.

EEUC [12] is a distributed unequal clustering algorithm which elects cluster heads based on the residual energy of nodes. Each node becomes a tentative cluster head with a probability T. Tentative cluster heads use uneven competition ranges to construct clusters of uneven sizes. The clusters closer to the BS have smaller sizes than those farther away from it, thus the cluster heads closer to the BS can preserve some energy for the intercluster data forwarding. In this way, the energy consumption among cluster heads is balanced. As the quality of the generated cluster heads is affected by T, there are “isolate points” in EEUC in some case of T.

3. Network Model and Problem Description

3.1. Network Model

To simplify the network model, we adopt a few reasonable assumptions as follows. (1)

There are N sensor nodes that are distributed randomly in an $M \times M$ square field.

(2)

All the nodes and the BS are stationary after deployment.

(3)

All the sensor nodes can be heterogeneous.

(4)

All the sensor nodes are location-unaware.

(5)

All the nodes can use power control to vary the amount of transmit power. The generated cluster heads can communicate with the BS directly.

(6)

The BS is out of the sensor field. It has a sufficient energy resource and the location of the BS is known by each node.

(7)

Each node has an identity ( $id$ ).

The energy model is adopted from [3].

To transmit an l-bit data to a distance d, the radio expends energy:

\begin{matrix} E_{T_{x}} (l, d) = {\begin{cases} l \times E_{elec} + l \times ϵ_{fs} \times d^{2}, & d < d_{0}, \\ l \times E_{elec} + l \times ϵ_{mp} \times d^{4}, & d \geq d_{0}, \end{cases} \end{matrix}

(1)

where d is the transmission distance.

E_{elec}

ϵ_{fs}

and

ϵ_{mp}

are parameters of the transmission/reception circuitry. Depending on the distance between the transmitter and receiver, free space (

ϵ_{fs}

) or multipath fading (

ϵ_{mp}

) channel models is used.

While receiving an l-bit data, the radio expends energy:

\begin{matrix} E_{R_{x}} (l) = l \times E_{elec} . \end{matrix}

(2)

Additionally, we assume that the energy for data sensing is $E_{sen}$ , and the energy for data aggregation is $E_{com}$ .

3.2. Problem Description

The properties of an effective clustering algorithm are usually summarized as follows. (1)

It is a distributed algorithm.

(2)

It can evenly generate cluster heads to balance the energy consumption among nodes.

(3)

It has acceptable algorithm overhead.

(4)

It has the ability to handle heterogeneous node issues [8].

By analyzing these properties above, two points which are also necessary for an effective clustering algorithm are missed. As we mentioned above, energy hole problem leads to a certain number of nodes dying prematurely, reducing the network lifetime. Therefore, an effective clustering algorithm should have a fifth property: (5)

it has the ability to solve “energy hole” problem.

Moreover, as mentioned above, in some case there are “isolate points” in EADEEG and EEUC protocol. For example, as shown in Figure 1: since the residual energy of node 5 is lower than the average energy of its neighbor nodes 8, 11, 12, and 14, its waiting time t for broadcasting the $H e a d_M s g$ is longer than T, in other word, it can not compete for cluster head before T, and it also can not receive any $H e a d_M s g$ s from the neighbor cluster heads 8, 11, 12, and 14, thus node 5 does not belong to any cluster, it becomes the “isolate point” and the area around it can not be monitored. For this problem, another property is absolutely necessary to be added: (6)

there exist no “isolate points” in the network.

Figure 1

The “isolate point” of EADEEG algorithm.

In this paper, a clustering algorithm EADUC satisfying the six properties is proposed. The details of EADUC are described in the next section.

4. EADUC Details

The whole operation is divided into rounds, where each round contents a setup phase and a data transmission phase just like LEACH. To form a clustering topology, the setup phase is divided into three subphases: neighbor node information collection phase, cluster head competition phase, and cluster formation phase; in the data transmission phase, cluster members collect local data from the environment, and send the collected data to the cluster heads, cluster heads receive and aggregate the data from their cluster members, and then send the aggregated data to the next hop nodes based on the routing tree we have constructed. Data transmission phase should be longer than setup phase to save the overhead of the algorithm and prolong the lifetime of the network. The state message of each node is listed in Table 1. Several control messages are needed and the description of these messages are shown in Table 2.

Table 1

Description of node state messages.

State	Description
$C a n d i d a t e$	Candidate node
$H e a d$	Head node
$P l a i n$	Plain node

Table 2

Description of control messages.

Message	Description
$N o d e_M s g$	Tuple (selfid, selfenergy)
$H e a d_M s g$	Tuple (selfid)
$J o i n_M s g$	Tuple (selfid, headid)
$S c h e d u l e_M s g$	Tuple (schedule, order)
$R o u t e_M s g$	Tuple (selfid, selfenergy)

4.1. Cluster Setup Phase

In the Network Deployment Phase

The BS broadcasts a signal at a certain power level. Each node can compute its approximate distance to the BS based on the received signal strength. There are three subphase in cluster setup phases: neighbor node information collection phase, whose duration is $T_{1}$ ; cluster head competition phase, whose duration is $T_{2}$ ; cluster formation phase, whose duration is $T_{3}$ .

In Neighbor Node Information Collection Phase

Each node broadcasts a $N o d e_M s g$ within radio r with the following two values: the node $i d$ and its residual energy $E_{r}$ . At the same time, it receives the $N o d e_M s g$ s from its neighbor nodes, according to which, each node calculates the average residual energy of its neighbor nodes $E_{a}$ by using the following formula:

\begin{matrix} E_{a} = \frac{1}{d} \sum_{i = 1}^{d} s_{i} \cdot E_{r}, \end{matrix}

(3)

where

s_{i}

denotes one of the neighbor nodes,

s_{i} \cdot E_{r}

denotes the residual energy of

s_{i}

, and d is the number of neighbor nodes.

For each node, we give the following formula to calculate its waiting time t for broadcasting $H e a d_M s g$ message;

\begin{matrix} t = {\begin{cases} \frac{E_{a}}{E_{r}} T_{2} V_{r}, & E_{r} \geq E_{a}, \\ T_{2} V_{r}, & E_{r} < E_{a}, \end{cases} \end{matrix}

(4)

where

E_{r}

is the residual energy of the node,

V_{r}

is a real value randomly distributed in

[0.9,1]

which is introduced to reduce the probability that two nodes send

H e a d_M s g

s at the same time.

After $T_{1}$ expires, it starts cluster head competition phase. For any node $s_{i}$ , in this phase, if it receives no $H e a d_M s g$ when time $t_{i}$ expires, it broadcasts the $H e a d_M s g$ within radio range $R_{C_{i}}$ to advertise that it will be a cluster head. Otherwise, it gives up the competition.

In order to generate unequal clusters, each node needs to calculate their own competition radius $R_{C}$ . The formula of $R_{C}$ in [12] is

\begin{matrix} R_{C} = [1 - c \frac{d_{\max} - d (s_{i}, DS)}{d_{\max} - d_{\min}}] R_{C}^{0}, \end{matrix}

(5)

where

d_{\max}

and

d_{\min}

are the maximum and minimum distance from the nodes in the network to the BS,

d (s_{i}, DS)

is the distance from node

s_{i}

to the BS, c is a weighted factor whose value is in

[0,1]

, and

R_{C}^{0}

is the maximum value of competition radius.

In heterogeneous networks, nodes have heterogeneous initial energy. In the case that each node has the same energy consumption, the nodes with low initial energy will die prematurely, reducing the network lifetime. In order to take full advantage of the high-energy nodes, the high-energy nodes should take more task. Therefore, considering the distance between nodes and the BS and the residual energy of nodes, we give the formula of $R_{C}$ :

\begin{matrix} R_{C} = [1 - α \frac{d_{\max} - d (s_{i}, BS)}{d_{\max} - d_{\min}} - β (1 - \frac{E_{r}}{E_{\max}})] R_{\max}, \end{matrix}

(6)

where

d (s_{i}, BS)

is the distance from node

s_{i}

to the BS, α and β is the weighted factors in

[0,1]

E_{r}

is the residual energy of node

s_{i}

, and

R_{\max}

is the maximum value of competition radius. From the above formula we can see that the competition radius of the node is determined by

d (s_{i}, BS)

and

E_{r}

. Large

d (s_{i}, BS)

and

E_{r}

generates a large

R_{C}

, which means that cluster heads with higher residual energy and farther away from the BS will control larger cluster areas. On one hand, cluster heads closer to the BS could save energy for data forwarding. On the other hand, cluster heads with lower residual energy control smaller clusters in order to avoid their premature death and prolong the network lifetime.

Cluster Formation Phase

It is the last subphase of cluster setup phase. Each noncluster-head node chooses the nearest cluster head and sends the $J o i n_M s g$ which contains the $i d$ and residual energy of this node. Each cluster head creates a node schedule list according to the received $J o i n_M s g$ s, and sends the schedule list to the cluster members by broadcasting $S c h e d u l e_M s g$ . Each cluster is composed of the nodes in the V oronoi cell around the cluster head. The following pseudocode gives the details of the whole cluster setup phase.

4.2. Data Transmission Phase

4.2.1. Intra-Cluster Communication

Cluster members sense and collect local data from the environment, and send the collected data to the cluster heads. This process is called intra-cluster communication. For simplification, cluster members communicate with cluster heads directly, just like LEACH.

4.2.2. Inter-Cluster Communication

Cluster heads receive and aggregate the data from their cluster members, and then send the aggregated data to the next hop nodes. Here, we introduce a threshold distance $D I S T_T H$ . If the distance from cluster head $s_{i}$ to the BS $d (s_{i}, BS)$ is less than $D I S T_T H$ , $s_{i}$ communicates with the BS directly. Otherwise, $s_{i}$ selects some nodes from its neighbor nodes to construct the candidate forwarding nodes set, and then it select one node from the set as the finally forwarding node according to a parameter “ $E_{relay}$ ”. Here we give the formula to compute the energy consumption $E_{relay}$ when cluster head $s_{i}$ chooses $s_{j}$ as its next hops;

\begin{matrix} E_{relay} = d^{2} (s_{i}, s_{j}) + d^{2} (s_{j}, BS) . \end{matrix}

(7)

So $s_{i}$ will select the node with the highest residual energy from the two nodes with the smallest “ $E_{relay}$ ” in the candidate forwarding nodes set. We will set a proper $D I S T_T H$ to guarantee any cluster heads can find its next hop. After this phase, all the cluster heads construct a tree with the BS being the root. The data is forwarded on the edges of the tree to the BS.

5. Protocol Analysis

Theorem 1.

There is at most one cluster head in the range of any CH with covered radius $R_{C}$ .

Proof.

As we state previously, $V_{r}$ in formula (4) ensures that different nodes have different waiting time. We assume that node $s_{i}$ has a shorter waiting time and broadcasts the $H e a d_M s g$ within radio range $R_{C i}$ . Thus, all the nodes within this range give up the competition and become CMs. Therefore, there is no more than one CH in the range of any CH with covered radius $R_{C}$ .

Theorem 2.

The cluster head set generated by EADUC can cover all the network nodes.

Proof.

(1) When $E_{r} \geq E_{a}$ , we have $t = (E_{a} / E_{r}) T_{2} V_{r}$ according to formula (4). Thus, we can obtain $t \leq T_{2}$ since $V_{r} \leq 1$ .

(2) When $E_{r} < E_{a}$ , we have $t = T_{2} V_{r}$ according to formula (4). Thus $t \leq T_{2}$ since $V_{r} \leq 1$ .

Therefore, we conclude that the waiting time of any node is smaller than $T_{2}$ . Thus, any expected cluster head will broadcast a $H e a d_M s g$ and become a cluster head before $T_{2}$ expired, which can avoid the generation of isolate points.

Theorem 3.

The overhead complexity of control messages in the network is $O (N)$ .

Proof.

At the beginning of each round, each node broadcasts a $N o d e_M s g$ . Thus, there are $N N o d e_M s g$ s in the whole network. In each round, each cluster member broadcasts a $J o i n_M s g$ while each cluster head broadcasts a $h e a d_M s g$ , a $S c h e d u l e_M s g$ , and a $R o u t e_M s g$ . Suppose the number of generated cluster head is k. The total number of $J o i n_M s g$ is $N - k$ , and the numbers of $h e a d_M s g$ , $S c h e d u l e_M s g$ , and $R o u t e_M s g$ message are all k. Thus, the total number of control messages in the whole network is $N + (N - k) + k + k + k = 2 N + 2 k$ . Therefore, the overhead complexity of control messages in the network is $O (N)$ .

Theorem 4.

EADUC has a processing time complexity of $O (1)$ .

Proof.

EADUC adopts a distributed clustering strategy. Thus, the time complexity of the entire network is equal to that of a single node $O (1)$ . In other words, the time complexity is a constant and has nothing to do with the network size.

From the above analysis, we can summarize the properties of EADUC as follows. (1)

It elects cluster heads based on the ratio between the average residual energy of neighbor nodes and the residual energy of the node itself. Nodes have relatively higher energy are elected, which is helpful in prolonging the network lifetime [8].

(2)

There are no “isolate points” in EADUC, which is proved in Theorem 2.

(3)

The competition radius $R_{C}$ takes into account both the distance to the BS and the residual energy of nodes. Unequal clusters generated by using $R_{C}$ will be more effective in prolonging the network lifetime.

(4)

From Theorems 1 and 2, there is one and only one cluster head in the range of any cluster head with covered radius $R_{C}$ . Here, we can draw the conclusion that, EADUC satisfies the six properties mentioned earlier.

There are three parameters in EADUC: α, β, and $R_{\max}$ . α and β determine the influence of the residual energy and the distances to the BS of nodes on cluster sizes. $R_{\max}$ is the maximum value of competition radius, which determines the number of generated cluster heads binding with α and β. We will discuss this issue further in the next section.

6. Simulations

The simulations were performed in NS-2, and two scenarios are chosen.

Homogeneous Scenario

The initial energy of each node in the network is 2 $J$ .

Heterogeneous Scenario

The initial energy of nodes in the network is uniformly distributed over the interval 1–3 $J$ .

The parameters of simulations are listed in Table 3.

Table 3

Parameters of the simulation.

Parameter	Value
Sensor field	$200 m \times 200 m$
BS location	(250, 100)
Number of nodes	100
Initial energy of nodes	2 $J$ , 1–3 $J$
Data packet size	500 $bytes$
$E_{elec}$	50 $nJ / bit$
$ϵ_{fs}$	10 $pJ / (bit \cdot m^{2})$
$ϵ_{mp}$	0.0013 $pJ / (bit \cdot m^{4})$
$E_{sen}$	0 $J / bit$
$E_{com}$	5 $nJ / (bit \cdot signal)$
$R_{\max}$	10–200 $m$

6.1. Cluster Head Distribution

We run EADUC in these scenarios, respectively. Figure 2 shows the relationship between the number of cluster heads and $R_{\max}$ when α and β choose different values. As shown in Figure 2, the curve of $α = 1, β = 1$ is higher than that of $α = 0.5, β = 0.5$ . Moreover, the curve of $α = 0, β = 0$ is the lowest. The reason is that, when $R_{\max}$ is fixed, the increase of α and β leads to the decrease of cluster radius. Furthermore, the number of cluster heads decreases with the increase of the radius, which means the number of generated cluster heads is determined by $R_{\max}$ , α, and β.

Figure 2

Number of cluster heads generated in the network.

We set $α = 0.5, β = 0.5$ , and $R_{\max} = 50$ and run EADUC. Figure 3 exhibits the distribution of the number of cluster heads in a certain number of randomly selected experiments. As shown in the figure, the number of cluster heads in EADUC is concentrated in a small range, which means that EADUC has a high stability and reliability.

Figure 3

Distribution of the number of cluster heads.

6.2. Network Lifetime

On network lifetime, there is no clear definition. According to the definitions given in [13], the lifetime of a WSN can be quantified using the following three kinds of metrics. (1)

The time from the deployment of the network to the death of the first node (first node dies, FND).

(2)

The time when a certain percent of nodes alive (percentage nodes alive, PNA).

(3)

The time when all the nodes are dead in the network (last node dies, LND).

Here, we define the network lifetime as percentage node alive (PNA). That is, the network lifetime is defined as the time when 90 percent of nodes are alive. We set $α = 0.5, β = 0.5$ , and run EADUC. Figure 4 shows the the network lifetime of EADUC when $R_{\max}$ is 10–200. From Figure 4, we can see that EADUC gets the maximal network lifetime when $R_{\max}$ is 120–160.

Figure 4

Network lifetime with different $R_{\max}$ .

Networks are not always homogeneous. Therefore, clustering algorithms should have the ability to handle heterogeneous nodes issues. We run EADUC in homogeneous and heterogeneous scenarios. When $α = 0.5, β = 0.5$ , and $R_{\max} =$ 150, the network lifetime of EADUC in these scenarios are shown in Figure 5.

Figure 5

Network lifetime in different scenarios.

From Figure 5, we can see that the network lifetime in heterogeneous scenario is slightly longer than that in homogeneous scenario. The reason is that EADUC elects cluster heads considering the residual energy of nodes, which can take advantage of the high-energy nodes in heterogeneous scenario and prolong the network lifetime. As a comparison experiment, we set $k = 5$ and run LEACH in the same scenarios. Figure 6 shows the comparison of network lifetime of LEACH in different scenarios.

Figure 6

Network lifetime of LEACH.

In Figure 6, the network lifetime in heterogeneous scenario is shorter. Since nodes in LEACH elect themselves by a probability without considering the residual energy, low-energy nodes may die prematurely and the network lifetime is reduced.

In heterogeneous scenario, we run LEACH, LEACH-M, HEED, EEUC, and EADUC to compare their performance in network lifetime. As shown in Figure 7, EADUC and EEUC perform far better than LEACH, LEACH-M, and HEED in prolonging network lifetime attributed to the consideration of energy.

Figure 7

Network lifetime.

7. Conclusions

In this paper, we propose an energy-aware distributed unequal clustering protocol EADUC, which elects cluster heads based on the ratio between the average residual energy of neighbor nodes and the residual energy of the node itself. The unequal competition radius of nodes which is used to construct unequal clusters is determined by the distance to the BS and the residual energy. There are no isolate points in EADUC. Besides, the cluster heads closer to the BS have smaller cluster sizes to preserve some energy for the intercluster data forwarding, which can balance the energy consumption among cluster heads and prolong the network lifetime. Furthermore, EADUC satisfies the properties of an effective clustering algorithm and can prolong the lifetime of the network significantly.

Algorithm 1

begin (cluster setup algorithm)

$s t a t e$ ← $C a n d i d a t e$

Broadcast $N o d e_M s g$

while ( $T_{1}$ has not expired) do

Receive $N o d e_M s g$

Update neighborhood table NT $[]$

end

t← broadcast delay time for competing a cluster head

while ( $T_{2}$ has not expired) do

if $C u r r e n t T i m e < t$ do

if receive a $H e a d_M s g$ from a neighbor NT $[i]$ do

$s t a t e$ ← $P l a i n$

NT $[i]$ . $s t a t e$ ← $H e a d$

else

Continue

end

else if $s t a t e = C a n d i d a t e$ do

$s t a t e$ ← $H e a d$

$R_{c}$ ← competing radius

Broadcast $H e a d_M s g$

end

while ( $T_{3}$ has not expired) do

if $s t a t e = P l a i n & &$ has not sent $J o i n_M s g$ do

Send $J o i n_M s g$ to the nearest cluster head

else if $s t a t e = H e a d$ do

Receive $J o i n_M s g$ from its neighbor $P l a i n$ nodes

end

if $s t a t e = H e a d$ do

Broadcast $S c h e d u l e_M s g$

end

Footnotes

Acknowledgments

This paper is sponsored by National Science Foundation under Grant no. 60373012 and 10871119 of China, National Science Foundation under Grant no. ZR2009GM009 and ZR2009AM013, and EDRP Foundation under Grant no. J10LG09.

References

Zhou

BPEC: an energy-aware distributed clustering algorithm in WSNs

Journal of Computer Research and Development 2009 46 5 723 730

2-s2.0-66149165558

X. B.

Chen

G. H.

The energy hole problem of nonuniform node distribution in wireless sensor networks

Chinese Journal of Computers 2008 31 2 1 9

Heinzelman

W. R.

Chandrakasan

Balakrishnan

Energy-efficient communication protocol for wireless microsensor networks

Proceedings of the 33rd Annual Hawaii International Conference on System Siences (HICSS '00)

January 2000

Maui, Hawaii, USA

1 10 223

2-s2.0-0033877788

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

Jia

Y. C.

Liu

Y. H.

Hierarchical clustering routing scheme based on LEACH in wireless sensor networks

Computer Engineering 2009 35 11 74 76

Kumar

Trilok

Patel

R. B.

EEHC: energy efficient heterogeneous clustered scheme for wireless sensor networks

Computer Communications 2009 32 4 662 667

2-s2.0-59849092261

10.1016/j.comcom.2008.11.025

Zhang

X. H.

Y. Z.

Algorithm of cluster head multi-hops based on LEACH

Computer Engineering and Design 2008 28 17 4158 4160

Liu

Cao

J. N.

Chen

G. H.

Chen

L. J.

Wang

X. M.

Gong

H. G.

EADEEG: an energy-aware data gathering protocol for wireless sensor networks

Journal of Software 2007 18 5 1092 1109

2-s2.0-34347254238

10.1360/jos181092

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.

An energy-efficient distributed clustering algorithm for wireless sensor networks

Computer Engineering 2011 37 3 83 86

11.

Soro

Heinzelman

W. R.

Prolonging the lifetime of wireless sensor networks via unequal clustering

Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS '05)

April 2005

Colorado, USA

236 243

2-s2.0-28444435877

12.

C. F.

Chen

G. H.

An energy-efficient unequal clustering mechanism for wireless sensor networks

Proceedings of the IEEE International Conference on Mobile Adhoc and Sensor Systems Conference

November

Washington, DC, USA

IEEE Press

1 8

13.

Gamwarige

Kulasekere

An algorithm for energy driven cluster head rotation in a distributed wireless sensor network

Proceedings of the International Conference on Information and Automation, (ICIA '05)

2005

Hong Kong

354 359

An Energy-Aware Distributed Unequal Clustering Protocol for Wireless Sensor Networks

Abstract

1. Introduction

2. Related Work

3. Network Model and Problem Description

3.1. Network Model

3.2. Problem Description

4. EADUC Details

4.1. Cluster Setup Phase

In the Network Deployment Phase

In Neighbor Node Information Collection Phase

Cluster Formation Phase

4.2. Data Transmission Phase

4.2.1. Intra-Cluster Communication

4.2.2. Inter-Cluster Communication

5. Protocol Analysis

Theorem 1.

Proof.

Theorem 2.

Proof.

Theorem 3.

Proof.

Theorem 4.

Proof.

6. Simulations

Homogeneous Scenario

Heterogeneous Scenario

6.1. Cluster Head Distribution

6.2. Network Lifetime

7. Conclusions

Algorithm 1

Footnotes

Acknowledgments

References