Advanced
NUND: Non-Uniform Node Distribution in Cluster-based Wireless Sensor Networks
NUND: Non-Uniform Node Distribution in Cluster-based Wireless Sensor Networks
KSII Transactions on Internet and Information Systems (TIIS). 2014. Jul, 8(7): 2302-2324
Copyright © 2014, Korean Society For Internet Information
  • Received : April 09, 2014
  • Accepted : May 06, 2014
  • Published : July 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Ju Ren
Department of Electrical and Computer Engineering, University of Waterloo Waterloo, Ontario, N2L 3G1, Canada
Yaoxue Zhang
School of Information Science and Engineering, Central South University Changsha, Hunan, 410083, China
Xiaodong Lin
Faculty of Business and Information Technology, University of Ontario Institute of Technology, Oshawa, Ontario, L1H 7K4, Canada

Abstract
Cluster-based 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 many-to-one traffic pattern in WSN, the network lifetime is generally deteriorated by the unbalanced energy consumption in a cluster-based WSN. Therefore, energy efficiency and network lifetime improvement are two crucial and challenging issues in cluster-based WSNs. In this paper, we propose a Non-Uniform Node Distribution (NUND) scheme to improve the energy efficiency and network lifetime in cluster-based WSNs. Specifically, we first propose an analytic model to analyze the energy consumption and the network lifetime of the cluster-based 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 cluster-based 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.
Keywords
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 resource-limited sensor nodes that sense targeted area periodically and deliver the sensed data to the sink via a multihop transmission. Since the sensor nodes are battery-powered 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, non-uniform 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 non-uniform 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 non-uniform node distribution approach to mitigate the unbalanced energy consumption in a corona-based WSN. Ferng et. al. [6] propose three non-uniform node distribution strategies to achieve completely balanced energy consumption, the longest network lifetime and the fewest sensor nodes cost respectively in a corona-based 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 cluster-based WSNs. Since the energy consumption and network lifetime are different between the hierarchical WSNs and flat WSNs, it is essential to investigate the non-uniform node distribution in cluster-based 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 Non-Uniform Node Distribution (NUND) scheme to improve the energy efficiency and network lifetime in cluster-based 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 cluster-based WSNs. The proposed analytic model considers the energy consumption not only for data gathering, but also for clustering.
(2) We propose a non-uniform 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 cluster-based 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 cluster-based 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 coverage-focused scheme, which focus on ensuring the network coverage and connectivity [7 , 8 , 9] . The other is the performance-focused 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 non-uniform 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 non-uniform node distribution approach to mitigate the unbalanced energy consumption in a corona-based WSN. They claim that the unbalanced energy consumption is unavoidable in a circular multihop sensor network with non-uniform 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 non-uniform 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 distance-based and a density-based 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 non-uniform node distribution. Lian et al. [12] propose a non-uniform 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 power-aware non-uniform node distribution scheme is presented in [13] to address the sink-routing hole problem and ensure a long-term 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 cluster-based 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 cluster-based WSNs [24 , 25] . Several existing works have investigated the energy consumption and network lifetime in cluster-based WSNs, which provide a basis for studying the node distribution schemes. Lee et al. [14] derive the upper bound on the network lifetime in cluster-based 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 cluster-based 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 cluster-based WSNs. Different from the existing works, we aim to propose a non-uniform 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 cluster-based 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, intra-cluster data aggregation and inter-cluster data transmission. In intra-cluster 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 inter-cluster 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 multi-hop wireless sensor and ad-hoc networks. In addition, the inter-cluster transmission is based on a collision-free 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).
PPT Slide
Lager Image
PPT Slide
Lager Image
Here, Eelec is the transmitting circuit loss. Both the free space ( d 2 power loss) and the multi-path 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
PPT Slide
Lager Image
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 cluster-based 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 cluster-based 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 cluster-based WSNs where the sensor nodes are uniformly deployed with the required node density. The data gathering model in cluster-based 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 Cl and the sink is l = hr + x , and the angle of the fan-shaped 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 fan-shaped 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 .
PPT Slide
Lager Image
The Analytic Model for Cluster-based WSNs
Since the data transmission in cluster-based 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 re-election. 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 Cl and the sink is l. Then if Ecch and Eccms denote the energy consumption of CH and CMs for clustering respectively, we have
PPT Slide
Lager Image
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 , Ecch = ( Eelec + εfs r 2 ) λ 1 + ( n - 1) Eelec λ 2 ; otherwise, Ecch = ( Eelec + εamp r 4 ) λ 1 + ( n -1) Eelec λ 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 . Therefore, we can determine the number of nodes in Q is y × × 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.
PPT Slide
Lager Image
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 intra-cluster 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 intra-cluster 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 Each and CMs Eacms during the intra-cluster data aggregation are
PPT Slide
Lager Image
where εk = εfs and α = 2, if r d 0 ; otherwise, εk = εamp and α = 4.
Proof. In the intra-cluster 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 intra-cluster data aggregation in a data period is
PPT Slide
Lager Image
Similar to the proof of Lemma 1 , we can calculate the energy consumption of CMs for intra-cluster data aggregation is
PPT Slide
Lager Image
Lemma 3. Denote the aggregation rate of the intra-cluster data is φ. We have, in a data period, the energy consumption of the CH in the inter-cluster data transmission Etch is
PPT Slide
Lager Image
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 inter-cluster data transmission consists of two parts, the energy consumption for sending its intra-cluster 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
PPT Slide
Lager Image
Therefore, the data amount received by the CH in a data period is Drch = φτρα ( 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 Dtch = φτρα ( R 2 - ( l - r ) 2 ).
In the inter-cluster 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
Etch = φτρα ( R 2 - ( l - r ) 2 )( Eelec + εk 1 lα 1 ) + φτρα ( R 2 - ( l + r ) 2 ) Eelec , 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 inter-cluster transmission is
Etch = φτρα ( R 2 - ( l - r ) 2 )( Eelec + εk 2 (2 r ) α2 ) + φτρα ( R 2 - ( l + r ) 2 ) Eelec , 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 re-elected every η data periods, the average energy consumption Elavg of the node whose distance to the sink is l is
PPT Slide
Lager Image
Proof. When the node acts as a CM, the energy consumption for intra-cluster data aggregation in a data period is Eacms / n , and the energy consumption for clustering is Eccms / n . When the node acts as the CH, the energy consumption for intra-cluster data aggregation and inter-cluster data transmission in a data period is Each + Etch , the energy consumed for clustering is Ecch / 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 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.
PPT Slide
Lager Image
Theorem 2. Denote the initial energy of the sensor nodes is E 0 . Therefore, the network lifetime is LT = E 0 / max( Elavg ) | 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( Elavg ) | l ∈ (0, R ], we can easily get LT = E 0 / max( Elavg ) | l ∈ (0, R ].
5. The Proposed NUND Scheme
- 5.1 The Non-Uniform 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 cluster-based 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 ET = E 0 / T , and the node density function is
PPT Slide
Lager Image
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 ET = E 0 / T . Therefore, if there are sensor nodes whose energy consumption in a data period is larger than ET , 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 ( Elavg / ET ) · ρ . However, the node density in the regions where the energy consumption of the sensor nodes are not larger than ET 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 mT =
PPT Slide
Lager Image
.
Proof. According to the node density function in Theorem 3, the number of sensor nodes should be mT =
PPT Slide
Lager Image
. Here, the symbol
PPT Slide
Lager Image
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 ET = E 0 / T . According to Theorem 4 , Fig. 2 shows the number of added nodes under the different ET after meeting the required node density. The shadow area indicates the region where needs to deploy additional nodes. It is shown that a smaller ET indicates a larger number of sensor nodes, while a smaller ET also indicates a longer network lifetime. And Fig. 3 shows the node density in different areas of the network under different ET .
PPT Slide
Lager Image
The number of added nodes under various ET
PPT Slide
Lager Image
Node density under various ET
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 Tm which makes m =
PPT Slide
Lager Image
, where
PPT Slide
Lager Image
Proof. Given a fixed number of sensor nodes m , we should first uniformly distribute ρπR 2 nodes to meet the coverage requirement. Denote Tm 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
PPT Slide
Lager Image
And Theorem 4 shows that the number of sensor nodes required to achieve the node density ρl is
PPT Slide
Lager Image
. Therefore, let m =
PPT Slide
Lager Image
, 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 Tm under a fixed number of sensor nodes m .
Determine the optimal network lifetime under a fixed number of sensor nodes
PPT Slide
Lager Image
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 ro under a fixed number of sensor nodes m .
Determine the optimal cluster radius under a fixed number of sensor nodes
PPT Slide
Lager Image
Determine the optimal cluster radius under a fixed number of sensor nodes
Based on the two algorithms above, we detail the non-uniform node distribution algorithm as follows.
Non-Uniform Node Distribution Algorithm
PPT Slide
Lager Image
Non-Uniform Node Distribution Algorithm
- 5.2 A Special Case of the NUND scheme
In the previous subsection, we detail the non-uniform 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 ρlall should be
PPT Slide
Lager Image
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( Elavg ) | l ∈ { l min , R }. Therefore, we can increase the node density of the areas whose energy consumption is higher than min( Elavg ) | l ∈ { l min , R }. Since min( Elavg ) | l ∈ { l min , R } is the minimum nodal energy consumption of the network, we have the density function ρlall should be
PPT Slide
Lager Image
Theorem 7 . To achieve balanced energy consumption, the number of sensor nodes required to be distributed is at least
PPT Slide
Lager Image
Proof. According to Theorem 4 , if we require a node density of ρl , the number of sensor nodes should be m =
PPT Slide
Lager Image
. Therefore, if the required node density is ρlall , we have
PPT Slide
Lager Image
.
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 ET . Compared to Fig. 2 where ET 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 ET 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.
PPT Slide
Lager Image
Required sensor nodes under different cluster radii to achieve balanced energy consumption
PPT Slide
Lager Image
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 inter-cluster 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
PPT Slide
Lager Image
Network Parameters for Simulations
- 6.1 Energy Consumption Evaluation
In this subsection, we evaluate our theoretical analysis on the energy consumption of the cluster-based 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.
PPT Slide
Lager Image
(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 ET = min(Elavg) , then we can get the optimal lifetime Tm = E0 / min(Elavg) .
- 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.
PPT Slide
Lager Image
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.
PPT Slide
Lager Image
(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.
PPT Slide
Lager Image
(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 inter-cluster 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.
PPT Slide
Lager Image
(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 Tm in NUND strategy. And, for any network lifetime T , the maximum nodal energy consumption in a data period should be ET = E0 / 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.
PPT Slide
Lager Image
(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 Non-Uniform Node Distribution (NUND) scheme to improve the energy efficiency and network lifetime under a fixed number of sensor nodes in cluster-based WSNs. To identify the hotspot of the network, we propose an analytic model to analyze the energy consumption and network lifetime of the cluster-based 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 non-uniform 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.
References
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 Cloud-Based Scheme for Protecting Source-Location Privacy against Hotspot-Locating 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 cluster-radius 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 “Data-centric 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 corona-based 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 “Energy-aware 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 non-uniform 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 “Power-aware 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 cluster-based 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 cluster-based routing protocol for wireless sensor networks with nonuniform node distribution” AEU-International 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 energy-efficient 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 Cluster-based MAC Protocol for Vehicular Ad-hoc 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, energy-efficient, 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 energy-efficient 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 Energy-Efficient Disjoint Multi-Path 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/Intrusion-Tolerant 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 event-driven 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 Chung-Shuo , Shieh Chin-Shiuh 2014 “Efficient Cluster Radius and Transmission Ranges in Corona-based 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