Clusterbased wireless sensor network (WSN) can significantly reduce the energy consumption by data aggregation and has been widely used in WSN applications. However, due to the intrinsic manytoone traffic pattern in WSN, the network lifetime is generally deteriorated by the unbalanced energy consumption in a clusterbased WSN. Therefore, energy efficiency and network lifetime improvement are two crucial and challenging issues in clusterbased WSNs. In this paper, we propose a NonUniform Node Distribution (NUND) scheme to improve the energy efficiency and network lifetime in clusterbased WSNs. Specifically, we first propose an analytic model to analyze the energy consumption and the network lifetime of the clusterbased WSNs. Based on the analysis results, we propose a node distribution algorithm to maximize the network lifetime with a fixed number of sensor nodes in clusterbased WSNs. Extensive simulations demonstrate that the theoretical analysis results determined by the proposed analytic model are consistent with the simulation results, and the NUND can significantly improve the energy efficiency and network lifetime.
1. Introduction
W
ireless sensor network (WSN) has emerged as a promising technology to monitor environment and collect information in both military and civilian operations
[1]
. A typical WSN consists of a large number of resourcelimited sensor nodes that sense targeted area periodically and deliver the sensed data to the sink via a multihop transmission. Since the sensor nodes are batterypowered and difficult to be recharged, energy efficiency is a crucial issue in WSNs
[2]
.
Clustering is an effective mechanism to improve the energy efficiency of WSNs
[3]
. The data aggregation at cluster heads greatly reduces the energy consumption for data forwarding. However, since the clusters close to the sink have to forward the aggregated data from the other clusters, they would exhaust their energy quickly and cause unbalanced energy consumption in the network. The unbalanced energy consumption finally leads to a premature death in the hotspot and deteriorates the network lifetime. Therefore, how to smooth the energy consumption of the hotspot is a critical issue to improve the network lifetime.
Recently, nonuniform node distribution has been proved as a feasible solution and attracted increasing attention in balancing the energy consumption of sensor nodes
[4
,
5
,
6]
. The basic idea of nonuniform node distribution is to add more nodes to the areas with heavier traffic to mitigate the unbalanced energy consumption. Wu et al.
[5]
propose a quantified nonuniform node distribution approach to mitigate the unbalanced energy consumption in a coronabased WSN. Ferng et. al.
[6]
propose three nonuniform node distribution strategies to achieve completely balanced energy consumption, the longest network lifetime and the fewest sensor nodes cost respectively in a coronabased WSN. Most of the existing works can smooth the unbalanced energy consumption of the network and improve the network lifetime. However, little attention has been paid to the node distribution study in clusterbased WSNs. Since the energy consumption and network lifetime are different between the hierarchical WSNs and flat WSNs, it is essential to investigate the nonuniform node distribution in clusterbased WSNs. In addition, most of the related works focus on balancing the energy consumption of the whole network and hence to maximize the network lifetime, which obviously requires a large number of sensor nodes and leads to a huge distribution cost.
In this paper, we propose a NonUniform Node Distribution (NUND) scheme to improve the energy efficiency and network lifetime in clusterbased WSNs under a fixed number of sensor nodes. The main contributions are concluded as follows.
(1) We propose an analytic model to analyze the energy consumption and network lifetime in clusterbased WSNs. The proposed analytic model considers the energy consumption not only for data gathering, but also for clustering.
(2) We propose a nonuniform node distribution algorithm to maximize the network lifetime with a fixed number of sensor nodes. The fully balanced energy consumption is also discussed in NUND as a special case, which is the sensor nodes are enough to smooth the nodal energy consumption in the whole network.
(3) Extensive simulations demonstrate that our analytic model can accurately estimate the energy consumption and network lifetime of clusterbased WSNs and the proposed NUND scheme can significantly improve the energy efficiency and network lifetime with a fixed distribution cost.
The reminder of this paper is organized as follows. Section 2 reviews the related works. Section 3 describes the system model and design goals. Section 4 analyzes the energy consumption and network lifetime of clusterbased WSNs. The proposed NUND scheme is detailed in Section 5. Section 6 shows the comparison between theoretical analysis and simulation results and evaluates the effectiveness of the NUND. Finally, we conclude the paper in Section 7.
2. Related Work
There has been plenty of related works on studying node distribution in WSNs
[4
,
5
,
6
,
7
,
8
,
9
,
10]
. We can briefly divide the existing works into two categories according to the different concerns. The one is the coveragefocused scheme, which focus on ensuring the network coverage and connectivity
[7
,
8
,
9]
. The other is the performancefocused scheme, which aim to improve the network performance (e.g., energy efficiency, network lifetime) after meeting the coverage and connectivity requirements
[4
,
5
,
6
,
10]
. In this paper, we concentrate on the latter and review the existing works in this section.
Olariu et. al.
[10]
first prove that the unbalanced energy consumption and energy hole problem is inevitable when the sensor nodes are distributed uniformly in the network and report data constantly. However, they discuss the energy hole problem in the WSNs with nonuniform node distribution in
[4]
and conclude that balanced energy consumption is possible when the data rates can be adjusted. Based on their analysis conclusions, Wu et al.
[5]
propose a quantified nonuniform node distribution approach to mitigate the unbalanced energy consumption in a coronabased WSN. They claim that the unbalanced energy consumption is unavoidable in a circular multihop sensor network with nonuniform node distribution and constant data reporting. Afterwards, a following work is done by Ferng et. al.
[6]
. They prove the feasibility of balanced energy consumption with a switch scheduling on the sensor node. And they propose three nonuniform node distribution schemes to achieve completely balanced energy consumption, the longest network lifetime and the fewest sensor nodes cost respectively. In
[11]
, Chang et al. present a distancebased and a densitybased node distribution scheme, to balance energy consumption and improve network lifetime. The former scheme is to control the node deployment distance and use power control mechanism to balance the energy consumption. And the latter is to adjust the density of sensor nodes which are switched between active and sleep modes in each zone.
Besides the schemes focusing on balancing the energy consumption of the network, a few related works try to improve other network performances (e.g., data capacity) with the nonuniform node distribution. Lian et al.
[12]
propose a nonuniform node distribution scheme to increase the data capability of WSNs. Sensor nodes in their scheme work in two modes: active mode and sleep mode. They propose a routing algorithm by dynamically changing the mode of the sensor nodes to save energy and a node distribution scheme to determine the node densities in different areas of the network. A poweraware nonuniform node distribution scheme is presented in
[13]
to address the sinkrouting hole problem and ensure a longterm connectivity in WSNs. They derive out a node distribution function based on the hop counts to the sink.
Most of the existing node distribution schemes can mitigate, even eliminate, the unbalanced energy consumption or improve the network performance in WSNs. However, little attention has been paid to the node distribution study in clusterbased WSNs. Clustering is proved as an efficient way to gather information in WSNs
[5
,
14
,
15
,
16]
, since the data aggregation at cluster heads can filter the redundant sensed data and significantly reduce the energy consumption of data forwarding. One the other hand, the energy consumption characteristics and the network lifetime are different in the hierarchical WSNs by the change of the data collection mechanism
[16
,
17
,
23]
. Therefore, it is essential to study how to distribute sensor nodes to smooth the unbalanced energy consumption in clusterbased WSNs
[24
,
25]
. Several existing works have investigated the energy consumption and network lifetime in clusterbased WSNs, which provide a basis for studying the node distribution schemes. Lee et al.
[14]
derive the upper bound on the network lifetime in clusterbased networks and investigate the effects of the number of clusters and spatial correlation on the network lifetime bound. Liu et al.
[5]
also investigate the lifetime time of clusterbased networks, and propose a routing protocol to improve the network FNDT based on unequal cluster radii.
In this paper, we propose an analytic model to estimate the energy consumption of sensor nodes and the network lifetime in clusterbased WSNs. Different from the existing works, we aim to propose a nonuniform node distribution scheme based on our analysis results to maximize the network lifetime with a fixed number of sensor nodes.
3. System Model and Design Goals
 3.1 Network Model
Consider the clusterbased WSN model that is also used in
[5]
.
n
homogeneous sensor nodes are deployed in a circular region of radius
R
and a static sink (or base station) situated at the center. The sensor nodes autonomously form a number of clusters with a uniform clustering algorithm
[5
,
18
,
19]
, such as EADC
[15]
where each cell head (CH) broadcasts clustering messages with the same transmission range. Therefore, each cluster will has a uniform cluster radius, denoted by
r
. When a sensor node is elected as a cluster head, it broadcasts clustering message to the neighboring nodes. And the sensor node chooses the nearest cluster head as its cluster head and send a joining message to the cluster head. All the sensor nodes periodically sense the monitored area and transmit the sensed data to the sink. The data transmission in each period consists of two procedures, intracluster data aggregation and intercluster data transmission. In intracluster data aggregation, each cluster member (CM) transmits its sensed data to the cluster head with a TDMA manner. Afterwards, the CH sends the aggregated data to the sink via a geographic greedy routing among the CHs during the intercluster data transmission. Geographic greedy routing is scalable for large WSNs, because it requires only local information for making forwarding decisions. This assumption has been widely adopted in analyzing multihop wireless sensor and adhoc networks. In addition, the intercluster transmission is based on a collisionfree MAC protocol without data loss just as the assumptions in
[4
,
5
,
6
,
10
,
11]
. The sensor nodes can be switched between active mode and sleep mode by a simple switching mechanism.
 3.2 Energy Consumption Model
According to the typical energy consumption model
[20
,
22]
, the energy consumption for transmitting sees Eq.(1) and the energy consumption for receiving is represented in Eq.(2).
Here,
E_{elec}
is the transmitting circuit loss. Both the free space (
d
^{2}
power loss) and the multipath fading (
d
^{4}
power loss) channel models are used in the model, depending on the distance between the transmitter and the receiver.
ε_{fs}
and
ε_{amp}
are respectively the energy required for power amplification in the two models.
l
denotes the bits of the data sent or received by a sensor node. The above parameter settings are shown in
Table 1
, which is adopted from
[3]
.
Network Parameters
 3.3 Design Goals
The objective of NUND is to distribute a fixed number of sensor nodes to maximize the network lifetime in clusterbased WSNs. Since coverage ratio is the primary requirement of WSNs, we should uniformly deploy the sensor nodes to meet the coverage requirement according to the existing node deployment schemes
[7
,
8
,
9]
. Therefore, the objective of NUND changes to distribute the rest sensor nodes to maximize the network lifetime. To be clearer, we first define the following terms.
Definition 1.
Required node density is the minimum node density to meet the required coverage ratio of the monitored area
.
Definition 2.
Since the deployed sensor nodes should meet the required coverage ratio, in this paper, network lifetime is defined as the duration from the time the network begins to work to the time when the density of alive nodes in an area is lower than the required node density. Since the sensor nodes periodically send sensed data to the sink, the network lifetime can be measured by the number of data periods (rounds)
.
Definition 3.
Distribution efficiency is defined as the ratio between the number of distributed sensor nodes and the network lifetime
.
With the definitions above, we specifically conclude our design goals as follows.
(1)
Accurately estimate the energy consumption and network lifetime
. Since NUND aims to distribute the rest sensor nodes to maximize the network lifetime after meeting the required node density, we should first accurately estimate the energy consumption and network lifetime in clusterbased WSNs when the node is uniformly distributed with the required node density. Then, we can distribute the rest sensor nodes to mitigate the unbalanced energy consumption and improve the network lifetime.
(2)
Maximize the distribution efficiency
. Since the distribution cost is an important factor in WSN applications, NUND should maximize the network lifetime with a fixed number of sensor nodes, which also means maximizing the distribution efficiency.
4. Analysis on Energy Consumption and Network Lifetime
In this section, we propose an analytic model to analyze the energy consumption and network lifetime in clusterbased WSNs where the sensor nodes are uniformly deployed with the required node density. The data gathering model in clusterbased WSNs is shown in
Fig. 1
(a). The monitored area of a cluster is described as the shadow area. Without loss of generality, we analyze the energy consumption of a cluster
c
where the distance between the cluster head
C_{l}
and the sink is
l
=
hr
+
x
, and the angle of the fanshaped shadow region is 2
α
. The analytic model is shown as
Fig. 1
(b). Denote
ρ
as the required node density and
r
as the cluster radius. According to the law of cosines, we have
α
= arccos(1 
r
^{2}
/ 2
l
^{2}
). To mitigate the overlap impact of neighbouring clusters, we consider the nodes in the fanshaped shadow region are the cluster members in the cluster
c
. And the area of the shadow region is 4
αlr
, therefore, there are
n
= 4
αlrρ
nodes in the cluster
c
.
The Analytic Model for Clusterbased WSNs
Since the data transmission in clusterbased WSNs consists of two procedures according to our network model, our analysis focuses on analyzing the nodal energy consumption in each procedure and determining the network lifetime based on the energy consumption characteristics. In most of existing works, the energy consumption only consists of the energy consumption in sensed data transmitting and receiving. In our analytic model, we consider the energy consumption for clustering and cluster head reelection. We detail our analysis with the following lemmas and theorems.
Lemma 1.
Denote the cluster radius as r and the required node density as ρ. Suppose that each clustering message takes
λ
_{1}
bits, and the joining message takes
λ
_{2}
bits. The distance between the cluster head C_{l} and the sink is l. Then if E_{c}^{ch} and E_{c}^{cms} denote the energy consumption of CH and CMs for clustering respectively, we have
where ε_{k}
=
ε_{fs} and α
= 2,
if r
≤
d
_{0}
;
otherwise, ε_{k}
=
ε_{amp} and α
= 4.
Proof.
According to the clustering process described in Sec. 3, the CH consumes energy in broadcasting the clustering message to cluster members and receiving the joining messages from them. Therefore, with the energy consumption model, we have if
r
≤
d
_{0}
,
E_{c}^{ch}
= (
E_{elec}
+
ε_{fs}
r
^{2}
)
λ
_{1}
+ (
n
 1)
E_{elec}
λ
_{2}
; otherwise,
E_{c}^{ch}
= (
E_{elec}
+
ε_{amp}
r
^{4}
)
λ
_{1}
+ (
n
1)
E_{elec}
λ
_{2}
.
Denote a small region of the cluster
c
as
Q
shown as
Fig. 1
(b). The distance between
Q
and the sink is
y
 {
l

r
≤
y
≤
l
+
r
}, and the width of
Q
is
dy
. Denote the angle between
Q
and the sink as
dθ
. Therefore, we can determine the number of nodes in
Q
is
y
×
dθ
×
dy
×
ρ
. Since
Q
is a very small region, we consider all the nodes in
Q
have the same distance to the cluster head. Therefore, we can calculate the distance between
Q
and the cluster head is 
L
^{2}
=
l
^{2}
+
y
^{2}
 2
ly
cos
θ
.
Since all the nodes in
Q
consume energy in receiving the clustering message and sending the jointing messages to the cluster head, the energy consumption in
Q
can be calculated as

λ2{yρEelec·dθ·dy+yρεfsL2·dθ·dy} +λ1yρEelec·dθ·dy.
Therefore, if we make integrals over the cluster
c
, we have the total energy consumption of all cluster members for clustering is
Lemma 1
shows the energy consumption of the CH and CMs for clustering respectively. In a data period, the cluster members send the sensed data to the cluster head with a TDMA manner in this intracluster data aggregation process. The CH first broadcasts the time slot message to CMs, and then, each CM transmits the sensed data to the CH in its allocated time slot. Therefore, we calculate the energy consumption for intracluster data aggregation in a data period as follows.
Lemma 2.
Denote the time slot message takes δ bits, and each CM sends τ bits of sensed data to the CH in its time slot. Then, in a data period, the energy consumption of CH E_{a}^{ch} and CMs E_{a}^{cms} during the intracluster data aggregation are
where ε_{k}
=
ε_{fs} and α
= 2,
if r
≤
d
_{0}
;
otherwise, ε_{k}
=
ε_{amp} and α
= 4.
Proof.
In the intracluster data aggregation, CH first broadcasts a time slot message to the CMs. After receiving the message, the CMs send
τ
bits data to the CH within their allocated time slots. Thus, the energy consumption of CH for intracluster data aggregation in a data period is
Similar to the proof of
Lemma 1
, we can calculate the energy consumption of CMs for intracluster data aggregation is
Lemma 3.
Denote the aggregation rate of the intracluster data is φ. We have, in a data period, the energy consumption of the CH in the intercluster data transmission E_{t}^{ch} is
where ε_{k}
_{1}
=
ε_{fs} and α
= 2,
if l
≤
d
_{0}
;
ε_{k}
_{1}
=
ε_{amp} and α
= 4,
if l
>
d
_{0}
;
ε_{k}
_{2}
=
ε_{fs} and α
= 2,
if
2
r
≤
d
_{0}
;
ε_{k}
=
ε_{amp} and α
= 4,
if
2
r
>
d
_{0}
.
Proof.
The energy consumption of CH in the intercluster data transmission consists of two parts, the energy consumption for sending its intracluster aggregated data and the energy consumption for receiving and forwarding the aggregated data from the upstream CHs. As shown in
Fig. 1
, the upstream area of the cluster can be calculated as
Therefore, the data amount received by the CH in a data period is
D_{r}^{ch}
=
φτρα
(
R
^{2}
 (
l
+
r
)
^{2}
). Since the data amount sent by the CH includes its own data and the data from the upstream CHs, the data amount sent by the CH in a data period is
D_{t}^{ch}
=
φτρα
(
R
^{2}
 (
l

r
)
^{2}
).
In the intercluster data transmission, the CH communicates with the sink directly if the distance to the sink
l
is no greater than 2
r
. Therefore, we have
E_{t}^{ch}
=
φτρα
(
R
^{2}
 (
l

r
)
^{2}
)(
E_{elec}
+
ε_{k}
_{1}
l^{α}
^{1}
) +
φτρα
(
R
^{2}
 (
l
+
r
)
^{2}
)
E_{elec}
, if
l
≤ 2
r
where
ε_{k}
_{1}
=
ε_{fs}
and
α
= 2, if
l
≤
d
_{0}
; otherwise,
ε_{k}
1 =
ε_{amp}
and
α
= 4.
If the distance between the CH and the sink is larger than 2
r
, it forwards the data to the next CH. Since the distance between two CHs is 2
r
, the energy consumption of the CH in intercluster transmission is
E_{t}^{ch}
=
φτρα
(
R
^{2}
 (
l

r
)
^{2}
)(
E_{elec}
+
ε_{k}
_{2}
(2
r
)
^{α2}
) +
φτρα
(
R
^{2}
 (
l
+
r
)
^{2}
)
E_{elec}
, if
l
≤ 2
r
where
ε_{k}
_{2}
=
ε_{fs}
and
α
= 2, if 2
r
≤
d
_{0}
; otherwise,
ε_{k}
_{2}
=
ε_{amp}
and
α
= 4.
Theorem 1.
If the CHs are reelected every η data periods, the average energy consumption E_{l}^{avg} of the node whose distance to the sink is l is
Proof.
When the node acts as a CM, the energy consumption for intracluster data aggregation in a data period is
E_{a}^{cms}
/
n
, and the energy consumption for clustering is
E_{c}^{cms}
/
n
. When the node acts as the CH, the energy consumption for intracluster data aggregation and intercluster data transmission in a data period is
E_{a}^{ch}
+
E_{t}^{ch}
, the energy consumed for clustering is
E_{c}^{ch}
/
n
. According to our network model, each sensor node have the same probability to be elected as the cluster head, therefore each node would act as CH for
η
rounds and as CM for (
n
1)
η
rounds within
nη
rounds. The average energy consumption of each node in a data period can be derived as the average of the energy consumption of being CH and CM as follows.
Theorem 2.
Denote the initial energy of the sensor nodes is
E
_{0}
.
Therefore, the network lifetime is LT
=
E
_{0}
/ max(
E_{l}^{avg}
) 
l
∈ (0,
R
].
Proof.
Since the network is uniformly deployed with required node density, the network lifetime is the time when the first sensor node dies. And the first dead sensor node of the network should be the node with the largest average energy consumption. Therefore, the network lifetime depends on the lifetime of the node with the heaviest energy consumption. Since the largest energy consumption is max(
E_{l}^{avg}
) 
l
∈ (0,
R
], we can easily get
LT
=
E
_{0}
/ max(
E_{l}^{avg}
) 
l
∈ (0,
R
].
5. The Proposed NUND Scheme
 5.1 The NonUniform Node Distribution Algorithm
In this section, we describe the NUND scheme in detail. According to the design goals in Sec. 3, the objective of NUND is to maximize the distribution efficiency. To be more specific, for a network with network radius
R
and required node density
ρ
, the objective of NUND is to distribute the
n
(
n
>
ρπR
^{2}
) sensor nodes to maximize the network lifetime.
First of all, we should uniformly deploy
n
_{min}
=
ρπR
^{2}
nodes to meet the minimum deployment requirements of the network. Denote
m
=
n

n
_{min}
, the problem changes to deploy the
m
nodes to maximize the network lifetime. In the previous section, we have analyzed the energy consumption and network lifetime in clusterbased WSNs where the nodes are uniformly distributed with the required node density
ρ
. Based on the analysis results, we detail the NUND scheme with the following theorems.
Theorem 3.
If we require the network lifetime is T, the maximum nodal energy consumption of the network in a data period should be E_{T}
=
E
_{0}
/
T , and the node density function is
Proof.
Since the network lifetime is determined by the maximum nodal energy consumption, if the required network lifetime is
T
, the maximum nodal energy consumption in a data period should be
E_{T}
=
E
_{0}
/
T
. Therefore, if there are sensor nodes whose energy consumption in a data period is larger than
E_{T}
, we should distribute more nodes in this area to mitigate the nodal energy consumption. Since the distributed nodes are assumed to share the energy consumption equally
[4
,
5
,
6]
, the distributed node density in this area should be (
E_{l}^{avg}
/
E_{T}
) ·
ρ
. However, the node density in the regions where the energy consumption of the sensor nodes are not larger than
E_{T}
can stay the same, since their lifetime of these nodes are larger than
T
.
Theorem 4.
If the required network lifetime is T, the number of sensor nodes that should be deployed is at least
m_{T}
=
.
Proof.
According to the node density function in Theorem 3, the number of sensor nodes should be
m_{T}
=
. Here, the symbol
is to ensure the number of sensor nodes is an integer.
According to
Theorem 3
,
Fig. 2
shows the nodal energy consumption per round in different regions of the network, where
R
= 400
m
,
r
= 70
m
and
ρ
= 0.00198. If the required network lifetime is
T
, we should ensure the maximal energy consumption of the network is below
E_{T}
=
E
_{0}
/
T
. According to
Theorem 4
,
Fig. 2
shows the number of added nodes under the different
E_{T}
after meeting the required node density. The shadow area indicates the region where needs to deploy additional nodes. It is shown that a smaller
E_{T}
indicates a larger number of sensor nodes, while a smaller
E_{T}
also indicates a longer network lifetime. And
Fig. 3
shows the node density in different areas of the network under different
E_{T}
.
The number of added nodes under various E_{T}
Node density under various E_{T}
The two theorems above prove the number of sensor nodes is required to achieve a specific network lifetime. Given a fixed number of sensor nodes
m
, the optimal network lifetime can be achieved is proven in the following theorem.
Theorem 5.
If the number of sensor nodes is
m
(
m
≥
ρπR
^{2}
),
the optimal network lifetime is
T_{m}
which makes
m
=
,
where
Proof.
Given a fixed number of sensor nodes
m
, we should first uniformly distribute
ρπR
^{2}
nodes to meet the coverage requirement. Denote
T_{m}
is the optimal network lifetime after we distribute the
m
sensor nodes. According to
Theorem 3
, we can calculate the node density of the network is
And
Theorem 4
shows that the number of sensor nodes required to achieve the node density
ρ_{l}
is
. Therefore, let
m
=
, we can calculate the optimal network lifetime Tm.
According to
Theorem 5
, for a given number of sensor nodes
m
, we can always distribute them to achieve the optimal network lifetime.
Algorithm 1
illustrates how to obtain the maximal network lifetime
T_{m}
under a fixed number of sensor nodes
m
.
Determine the optimal network lifetime under a fixed number of sensor nodes
Determine the optimal network lifetime under a fixed number of sensor nodes
Based on
Algorithm 1
, we can determine the optimal network lifetime with a fixed number of sensor nodes. However, we find the cluster radius has a significant impact on the average energy consumption of sensor nodes and the network lifetime, according to
Theorem 1
and
2
. Therefore, if the number of sensor nodes
m
is fixed, we can still improve the network lifetime by determining the optimal cluster radius.
Algorithm 2
illustrates how to choose the optimal cluster radius
r_{o}
under a fixed number of sensor nodes
m
.
Determine the optimal cluster radius under a fixed number of sensor nodes
Determine the optimal cluster radius under a fixed number of sensor nodes
Based on the two algorithms above, we detail the nonuniform node distribution algorithm as follows.
NonUniform Node Distribution Algorithm
NonUniform Node Distribution Algorithm
 5.2 A Special Case of the NUND scheme
In the previous subsection, we detail the nonuniform node distribution scheme. If we have enough sensor nodes (i.e.,
m
is large enough), a balanced energy consumption of the whole network can be achieved. In this subsection, we discuss the fully balanced energy consumption of the network as a special case of the proposed NUND scheme.
Theorem 6.
To achieve balanced energy consumption, the node density function of the network ρ_{l}^{all} should be
Proof.
To balance the energy consumption of the network, the average energy consumption in all the areas of the network should be reduced to min(
E_{l}^{avg}
) 
l
∈ {
l
_{min}
,
R
}. Therefore, we can increase the node density of the areas whose energy consumption is higher than min(
E_{l}^{avg}
) 
l
∈ {
l
_{min}
,
R
}. Since min(
E_{l}^{avg}
) 
l
∈ {
l
_{min}
,
R
} is the minimum nodal energy consumption of the network, we have the density function
ρ_{l}^{all}
should be
Theorem 7
.
To achieve balanced energy consumption, the number of sensor nodes required to be distributed is at least
Proof.
According to
Theorem 4
, if we require a node density of
ρ_{l}
, the number of sensor nodes should be
m
=
. Therefore, if the required node density is
ρ_{l}^{all}
, we have
.
Fig. 4
shows the comparison of network lifetime and the number of sensor nodes that should be deployed to achieve fully balanced energy consumption under different cluster radii. It is shown that balanced energy consumption means setting the minimum energy consumption of the network as the energy line
E_{T}
. Compared to
Fig. 2
where
E_{T}
is a variant value,
Fig. 4
is just a special case of the NUND scheme. It is also can be seen from
Fig. 4
that the energy consumption is different under different cluster radii, so the energy line
E_{T}
and the number of required sensor nodes are different to achieve a fully balanced energy consumption. The distribution efficiency will be maximized when the cluster radius
r
is 50m.
Fig. 5
shows the node densities in different areas of network when achieving balanced energy consumption under different cluster radii.
Required sensor nodes under different cluster radii to achieve balanced energy consumption
Node densities in different areas under different cluster radii to achieve balanced energy
6. Simulation Evaluation
We evaluate the proposed NUND scheme in OMNET++. We setup a simulation where CHs encapsulate every 100 bits of gathering data into a packet and then send the data packets to the sink during the intercluster transmission. If there are no special explanations for parameters, all the simulation parameters are adopted from
Table 1
and
Table 2
. We compare the proposed NUND scheme with the Uniform Node Distribution (UND) scheme.
Network Parameters for Simulations
Network Parameters for Simulations
 6.1 Energy Consumption Evaluation
In this subsection, we evaluate our theoretical analysis on the energy consumption of the clusterbased WSN.
Fig. 6
(a) shows the average energy consumption per round under various cluster radius, where the network radius
R = 400m
and the number of sensor nodes
N = 1500
.
Fig. 6
(b) shows the average energy consumption per round under different node densities. It is shown that our theoretical analysis is consistent with the simulation results. And it can be seen from
Fig. 10
that the average energy consumption is not impacted by the increment of the node density when the sensor nodes are distributed uniformly.
(a) Energy consumption per round under different cluster radii; (b) Energy consumption per round under different node densities.
 6.2 Balanced Energy Consumption of NUND
Since the balanced energy consumption of the network is a special case of NUND, we evaluate the idea network lifetime and energy efficiency of NUND in this subsection. According to
Theorem 3
, the average energy consumption in different areas of the network should be reduced to
E_{T} = min(E_{l}^{avg})
, then we can get the optimal lifetime
T_{m} = E_{0} / min(E_{l}^{avg})
.
 6.2.1 Energy Consumption
We compare the nodal energy consumption of NUND and UND. The experiment data of this section is generated as follows. Distribute the sensor nodes according to these two deployment strategies, and then record the energy consumption until the sink cannot receive any data.
Fig. 7
(a) and
Fig. 7
(b) show the status of each sensor node in NUND when the network dies under
R = 300m
and
R = 400m
respectively.
Fig. 7
(c) shows the status of each sensor node in UND when the network dies. In the three figures, the white nodes are the dead nodes and the black ones are those still alive. Correspondingly,
Fig. 7
(d),
Fig. 7
(e) and
Fig. 7
(f) show the residual energy of each node when the network dies. From
Fig. 7
(c) and
7
(f), it can be easily seen that there is a huge amount of energy left in UND, since the energy consumption of the hotspot is greatly larger than the other regions. Reversely,
Fig. 7
(d) and
7
(e) show that the residual energy in NUND is approximately zero, which indicates the perfect energy efficiency of NUND.
When the network dies, (a) Nodal status in NUND (R=300m, r=80m); (b) Nodal status in NUND (R=400m, r=80m); (c) Nodal status in UND (R=400m, r=80m); (d) Nodal residual energy in NUND (R=300m, r=80m); (e) Nodal residual energy in NUND (R=400m, r=80m); (f) Nodal residual energy in UND (R=400m, r=80m).
 6.2.2 Network lifetime and residual energy
Fig. 8
(a) shows the number of data packets received by the sink in different data periods. It is shown that the number of data packets received by the sink stays stable during a long time and plummet to zero only after several data periods.
Fig. 8
(b) shows the total energy consumption of all the sensor nodes in different data periods. Similar with
Fig. 8
(a), the energy consumption experiences minor fluctuations during a long time and plummet to zero after several data period. It indicates all sensor nodes completely exhaust their energy simultaneously.
Fig. 8
(c) shows the number of dead nodes in different data periods.
Fig. 8
(d) shows the number of dead nodes in different data periods under UND. It can be seen that sensor nodes die gradually until the network dies. Therefore, it can be seen from
Fig. 10
that the energy consumption of all the sensor nodes is balanced in NUND, which leads to a perfect energy efficiency. While the sensor nodes gradually die in NUD causing poor network efficiency.
(a) Data packets received by the sink in different data periods (NUND); (b) Total energy consumption of the network in different data periods (NUND); (c) Dead nodes in different data periods (NUND); (d) Dead nodes in different data periods (UND).
Fig. 9
(a) shows the comparison of the number of sensor nodes required to achieve the balanced energy consumption under different cluster radii and network radii. As shown in the figure, the number of required sensor nodes grows linearly with the increase of network radius when the cluster radius is fixed. However, when the network radius is fixed, the number of required sensor nodes decreases with the increasing cluster radius. This is because the cluster radius directly impacts the average energy consumption of the sensor nodes. Meanwhile, if we aim to balance the energy consumption to achieve a longer network lifetime, the number of required sensor nodes would be larger. However, we still can find the optimal cluster radius to maximize the distribution efficiency.
(a) Required sensor nodes for balanced energy consumption (NUND); (b) Network Lifetime under different cluster radii (NUND); (c) Residual energy ratio under different cluster radii (NUND); (d) Distribution efficiency under different cluster radii (NUND).
Fig. 9
(b) and
9
(c) shows the network lifetime and residual energy comparison in NUND and UND under different cluster radii. It can be seen from
Fig. 9
(b), the network lifetime in NUND is obviously longer than in UND, and under some cluster radii, the improvement ratio is nearly 100%.
Fig. 9
(c) shows that, the residual energy ratio decrease with the increasing cluster radius both in NUND and UND, but the residual energy ratio in NUND is much less than in UND. This is because, in our network model, the transmission range of intercluster communication rises with the increasing cluster radius, which directly impacts the residual energy ratio of the network. A larger cluster radius causes fewer nodes isolated in the network, and a lower residual energy ratio of the network.
Fig. 9
(d) shows the network efficiency of NUND under different cluster radii. It is shown that a smaller network would achieve higher network efficiency when the cluster radius is fixed. But when the network radius is a fixed number, the network efficiency increases first and then decreases. The peak value is achieved at between 40m and 50m. Therefore, it also indicates that we can find the optimal cluster radius to achieve the highest network efficiency.
 6.2.3 The impact of the required node density on network performance
In this subsection, we aim to evaluate the impact of the required node density on the network performance.
Fig. 10
(a) shows the comparison of data packets received by the sink under different node density. Obviously, if the required node density were larger, the number of data packets received by the sink would become larger since the number of sensor nodes is increased.
Fig. 10
(b) shows the nodal average energy consumption comparison under different required node densities. It is shown that the average energy consumption stays stable when the node density increases. Since the network lifetime depends on the average energy consumption, it indicates the network lifetime would not be impacted by the increment of the node density when the nodes are uniformly distributed in the network.
(a) Data packets received by the sink in different data periods (NUND); (b) Average energy consumption in different data periods (NUND).
 6.3 NUND with Limited Sensor Nodes
In this section, we evaluate the performance of the NUND with a fixed number of sensor nodes. According to
Theorem 5
, for
m
sensor nodes, we can always obtain the optimal network lifetime
T_{m}
in NUND strategy. And, for any network lifetime
T
, the maximum nodal energy consumption in a data period should be
E_{T} = E_{0} / T
, which is also called
energy line
. Therefore, the simulations in this section are based on different energy consumption lines to analyze the performance of NUND.
Fig. 11
(a) shows the node densities of different areas in the network under different energy lines. It is shown that when the number of sensor nodes is limited, the sensor nodes should be first distributed to the areas with highest average energy consumption, which is also called as hotspot. And the node density increases with the decline of the energy line.
Fig. 11
(b) shows the network lifetime comparison under different energy lines. Since the lower energy line means the larger number of sensor nodes, it can be seen from the figure that the network lifetime increases with the decreasing energy lines.
(a) Node density under different energy lines; (b) Network lifetime under different energy lines; (c) Required sensor nodes under different energy lines and cluster radii; (d) Distribution efficiency under different energy lines and cluster radii.
Fig. 11
(c) shows the required sensor nodes comparison under different energy lines in NUND. It is shown that the number of required sensor nodes increases with the decreasing energy line when the cluster radius is fixed. However, if the energy line is fixed, the number of required sensor nodes increases first and then decreases. The peak value is achieved when the cluster radius is 50m.
Fig. 11
(d) shows the distribution efficiency comparison under different energy lines and cluster radii. Similar with the
Fig. 11
(c), the optimal network efficiency is achieved at the cluster radius of 50m, when the energy line is fixed. Meanwhile, the distribution efficiency increases with the decline of the energy line. It indicates that the more sensor nodes would lead to better distribution efficiency before we achieve balanced energy consumption in the network, while the distribution efficiency can be maximized by choosing the optimal cluster radius.
7. Conclusion
In this paper, we have proposed a NonUniform Node Distribution (NUND) scheme to improve the energy efficiency and network lifetime under a fixed number of sensor nodes in clusterbased WSNs. To identify the hotspot of the network, we propose an analytic model to analyze the energy consumption and network lifetime of the clusterbased WSNs. Since the analysis results show the cluster radius causes a significant impact on the network lifetime, we present an algorithm to determine the optimal cluster radius. Further, we propose a nonuniform node distribution algorithm to distribute the fixed number of sensor nodes to maximize the network lifetime. Extensive simulations demonstrate the proposed analytic model can accurately predict the energy consumption and network lifetime, and the NUND significantly improve the energy efficiency and network lifetime. In our future work, we will focus on the node distribution in energy harvesting WSNs. Since sensor nodes are supplied by the stochastic renewable energy, the node distribution will be complicated due to the change of the energy consumption characteristics.
BIO
Ju Ren received the B.Sc. degree and M.Sc. degree both in Computer Science from Central South University, China, in 2009 and 2012, respectively. He has been working toward a Ph.D. degree in Computer Science from Central South University since 2012.9. Currently, he is a visiting scholar in the Department of Electrical and Computer Engineering, University of Waterloo, Canada. His research interests include wireless sensor networks, mobile smartphone sensing, cloud computing and transparent computing.
Yaoxue Zhang received the B.Sc. degree from Northwest Institute of Telecommunication Engineering, China, and the Ph.D. degree in computer networking from Tohoku University, Japan in 1989. Then, he joined the Department of Computer Science, Tsinghua University, China. He was a visiting professor of Massachusetts Institute of Technology and University of Aizu, in 1995 and 1998, respectively. Additionally, he serves as an editorial board member of four international journals. His major research interests include computer networking, operating systems, ubiquitous/pervasive computing, transparent computing, and active services. He has published more than 170 technical papers in international journals and conferences, as well eight monographs and textbooks. Currently, he is a fellow of the Chinese Academy of Engineering and a professor in computer science and technology in Central South University, China.
Xiaodong Lin received the Ph.D. degree in information engineering from Beijing University of Posts and Telecommunications, China, in 1998 and the Ph.D. degree (with Outstanding Achievement in Graduate Studies Award) in electrical and computer engineering from the University of Waterloo, Ontario, Canada, in 2008. Currently, he is an associate professor of information security with the Faculty of Business and Information Technology, University of Ontario Institute of Technology, Oshawa, Canada. His research interests include wireless network security, applied cryptography, computer forensics, and software security. He was the recipient of Natural Sciences and Engineering Research Council of Canada (NSERC) Canada Graduate Scholarships (CGS) Doctoral and the Best Paper Awards of the IEEE International Conference on Computer Communications and Networks (ICCCN 2009) and the IEEE International Conference on Communications (ICC 2007)—Computer and Communications Security Symposium. He is a senior member of the IEEE.
Zhang Y.
,
He S.
,
Chen J.
,
Sun Y.
,
Shen X.
2013
"Distributed Sampling Rate Control for Rechargeable Sensor Nodes with Limited Battery Capacity"
IEEE Transactions on Wireless Communications
Article (CrossRef Link)
12
(6)
3096 
3106
DOI : 10.1109/TCOMM.2013.050613.121698
Mahmoud M. E.
,
Shen X.
2012
"A CloudBased Scheme for Protecting SourceLocation Privacy against HotspotLocating Attack in Wireless Sensor Networks"
IEEE Transactions on Parallel and Distributed Systems
Article (CrossRef Link)
23
(10)
1805 
1818
DOI : 10.1109/TPDS.2011.302
Liu A.
,
Wu X.
,
Chen Z.
,
Gui W.
2010
“Research on the energy hole problem based on unequal clusterradius for wireless sensor networks”
Computer Communications
Article (CrossRef Link)
33
(3)
302 
321
DOI : 10.1016/j.comcom.2009.09.008
Stojmenovic I.
,
Olariu S.
2005
“Datacentric protocols for wireless sensor networks” Handbook of Sensor Networks
Article (CrossRef Link)
417 
456
Wu X.
,
Chen G.
,
Das S.
2008
“Avoiding energy holes in wireless sensor networks with nonuniform node distribution”
IEEE Transactions on Parallel Distributed Systems
Article (CrossRef Link)
19
(5)
710 
720
DOI : 10.1109/TPDS.2007.70770
Ferng H.W.
,
Hadiputro M.
,
Kurniawan A.
2011
“Design of novel node distribution strategies in coronabased wireless sensor networks”
IEEE Transactions on Mobile Computing
Article (CrossRef Link)
10
(9)
1297 
1311
DOI : 10.1109/TMC.2010.241
Liu Benyuan
,
Olivier Dousse
,
Philippe Nain
,
Don Towsley
2013
"Dynamic coverage of mobile sensor networks"
IEEE Transactions on Parallel and Distributed Systems
Article (CrossRef Link)
24
(2)
301 
311
DOI : 10.1109/TPDS.2012.141
Amac Guvensan M.
,
Gokhan Yavuz A.
2011
"On coverage issues in directional sensor networks: A survey"
Ad Hoc Networks
Article (CrossRef Link)
9
(7)
1238 
1255
DOI : 10.1016/j.adhoc.2011.02.003
He S.
,
Chen J.
,
Li X.
,
Shen X.
,
Sun Y.
2012
“Leveraging Prediction to Improve the Coverage of Wireless Sensor Networks”
IEEE Transaction on Parallel and Distributed Systems
Article (CrossRef Link)
23
(4)
701 
712
DOI : 10.1109/TPDS.2011.180
Olariu S.
,
Stojmenovic I.
2006
“Design guidelines for maximizing lifetime and avoiding energy holes in sensor networks with uniform distribution and uniform reporting”
in Proc. of IEEE International Conf. on Computer Communications
Article (CrossRef Link)
1 
12
Chang C.Y.
,
Chang H.R.
2008
“Energyaware node placement, topology control and mac scheduling for wireless sensor networks”
Computer Networks
Article (CrossRef Link)
52
(11)
2189 
2204
DOI : 10.1016/j.comnet.2008.02.028
Lian J.
,
Naik K.
,
Agnew G.B.
2006
“Data capacity improvement of wireless sensor networks using nonuniform sensor distribution”
International Journal of Distributed Sensor Networks
Article (CrossRef Link)
2
(2)
121 
145
DOI : 10.1080/15501320500201276
Liu Y.
,
Ngan H.
,
Ni L
2006
“Poweraware node deployment in wireless sensor networks”
International Journal of Distributed Sensor Networks
Article (CrossRef Link)
2
(2)
225 
241
Lee S.
,
Lee H.
2010
“Analysis of network lifetime in clusterbased sensor networks”
IEEE Communication Letter
Article (CrossRef Link)
14
(10)
900 
902
DOI : 10.1109/LCOMM.2010.081910.101093
Yu J.
,
Qi Y.
,
Wang G.
,
Gu X.
2012
“A clusterbased routing protocol for wireless sensor networks with nonuniform node distribution”
AEUInternational Journal of Electronics and Communications
Article (CrossRef Link)
66
(1)
54 
61
DOI : 10.1016/j.aeue.2011.05.002
Ren J.
,
Zhang Y.
,
Liu K.
2013
“An energyefficient cyclic diversionary routing strategy against global eavesdroppers in wireless sensor networks”
International Journal of Distributed Sensor Networks
Article ID 834245, Article (CrossRef Link)
2013
1 
15
Hafeez K.A.
,
Zhao L.
,
Mark J.W.
,
Shen X.
,
Niu Z.
2013
“Distributed Multichannel and Mobility Aware Clusterbased MAC Protocol for Vehicular Adhoc Networks”
IEEE Transactions on Vehicular Technology
Article (CrossRef Link)
62
(8)
3886 
3902
DOI : 10.1109/TVT.2013.2258361
Younis Ossama
,
Sonia Fahmy
2004
“HEED: a hybrid, energyefficient, distributed clustering approach for ad hoc sensor networks”
IEEE Transactions on Mobile Computing
Article (CrossRef Link)
3
(4)
366 
379
DOI : 10.1109/TMC.2004.41
Li Qing
,
Zhu Qingxin
,
Wang Mingwen
2006
“Design of a distributed energyefficient clustering algorithm for heterogeneous wireless sensor networks”
Computer Communications
Article (CrossRef Link)
29
(12)
2230 
2237
DOI : 10.1016/j.comcom.2006.02.017
Liu A.
,
Zheng Z.
,
Zhang C.
,
Chen Z.
,
Shen X.
2012
“Secure and EnergyEfficient Disjoint MultiPath Routing for WSNs”
IEEE Transactions on Vehicular Technology
Article (CrossRef Link)
61
(7)
3255 
3265
DOI : 10.1109/TVT.2012.2205284
Zeng R.
,
Jiang Y.
,
Lin C.
,
Fan Y.
,
Shen X.
2012
“A Distributed Fault/IntrusionTolerant Sensor Data Storage Scheme Based on Network Coding and Homomorphic Fingerprinting”
IEEE Trans. on Parallel and Distributed Systems
Article (CrossRef Link)
23
(10)
1819 
1830
DOI : 10.1109/TPDS.2011.294
Liu A.
,
Ren J.
,
Li X.
,
Chen Z.
,
Shen X.
2012
"Design Principles and Improvement of Cost Function based Energy Aware Routing Algorithms for Wireless Sensor Networks"
Computer Networks
Article (CrossRef Link)
56
(7)
1951 
1967
DOI : 10.1016/j.comnet.2012.01.023
Noori M.
,
Ardakani M.
2011
“Lifetime analysis of random eventdriven clustered wireless sensor networks”
IEEE Transactions on Mobile Computing
Article (CrossRef Link)
10
(10)
1448 
1458
DOI : 10.1109/TMC.2010.254
Lai Wei Kuang
,
Fan ChungShuo
,
Shieh ChinShiuh
2014
“Efficient Cluster Radius and Transmission Ranges in Coronabased Wireless Sensor Networks”
KSII Transactions on Internet and Information Systems
Article (CrossRef Link)
8
(4)
1237 
1255
Ghim Hojin
,
Kim Dongwook
,
Kim Namgi
2013
“Autonomous Deployment in Mobile Sensor Systems”
KSII Transactions on Internet and Information Systems
Article (CrossRef Link)
7
(9)
2173 
2193
DOI : 10.3837/tiis.2013.09.006