# A Type of Energy Hole Avoiding Method Based on Synchronization of Nodes in Adjacent Annuluses for Sensor Network

Authors: Chao Sha; Huan Chen; Chen Yao; Yao Liu; Ru-chuan Wang
Journal: International Journal of Distributed Sensor Networks
 (2016)

---

## Abstract

For the purpose of balancing energy consumption of nodes in Wireless Sensor Networks (WSNs for short), a type of energy hole avoiding method based on synchronization of nodes in adjacent annuluses (SNAA for short) is proposed in this paper. The circular network is divided into virtual annuluses with the same width. Nodes are deployed nonuniformly and their number increases in geometric progression from the outer annuluses to the inner ones which could effectively reduce the work load on nodes near the center. Moreover, each node could find its optimal parent by considering the residual energy of each candidate as well as the distance between the two nodes in adjacent annuluses. And on the basis of synchronization of nodes between adjacent annuluses during their transmitting and receiving phases, a sleep scheduling strategy is also proposed to further reduce the energy consumption of nodes in idle listening mode. Simulation results show that SNAA has a superior performance on energy consumption balance compared to the algorithm proposed (Liu et al., 2013; Wu et al., 2008) and it could also mitigate the energy hole problem in WSNs.


---

## Body

## 1. Introduction

In WSNs, sensor node usually behaves as both data originator and the router [1, 2]. The traffic follows a many-to-one pattern, where nodes nearer to the sink carry heavier traffic loads. Furthermore, they also tend to consume more energy as they are responsible for receiving and forwarding data from the whole network. It leads to a nonuniform energy consumption among nodes, that is, the “energy hole problem” [3]. No more data can be delivered to the sink after an energy hole appears. Moreover, nodes near the energy hole are required to bear the data load of those death nodes so that the energy consumption level will increase more rapidly, leading to extension of the hole, which is called funneling effect [4], and finally premature death or standstill of the entire network. Study shows that, because of the impact of the energy hole, the network residual energy is as high as 90% [5–7] when the network is out of function.On the other hand, energy balance is also key metrics impacting on the performance of WSNs. One of the most efficient methods to achieve energy balance is to optimize the deployment and configuration of WSNs [8–10]. Currently, random broadcasting and uniform clustering methods are adopted in most multihop networks [11]. By communicating among nodes and sleep scheduling, it could save more energy to extend network lifetime. However, it is difficult to achieve an energy balance [12]. Therefore, how to design a flexible deployment and broadcasting model for nodes is a chief problem in WSNs [13].


## 2. Related Works

In recent years, maximizing the network lifetime and energy balancing of WSNs have drawn much attention [1, 4]. Many different schemes have come forward adopting different means to prolong network lifetime and increase energy efficiency. CH rotation schemes, for example, LEACH [14] and HEED [15], are proposed to balance the energy consumption by periodically performing CH rotation among all sensor nodes in cluster. However, random number of CHs in each round causes uneven energy consumption leading to formation of energy hole [5, 7].


### 2.1. Nonuniform Node Distribution Strategy for Mitigating the Energy Hole Problem

Li and Mohapatra [16] present the first mathematical model towards the characterization of the energy hole problem. They consider sensor nodes distributed following the URP (Uniform Random Placement) law in a circular region divided into concentric coronas. They observe the impact of the following four factors on the energy hole problem: node density, hierarchical deployment, source bit rate, and traffic compression. They show that simply adding more nodes to the network does not solve the problem. By computing network lifetime after deployment, Hou et al. [17] adjust the location of relay nodes to maximize the network lifetime. But this method takes a heavy cost for the process of iteration and cannot adapt itself to varied networks.Liu et al. [4] proposed that node density should be proportional to the distance from sink. They formulated algorithms for deployment of nodes to achieve application required first node die time (FDT) and all nodes die time (ADT). Furthermore, they also proved that network lifetime can be maximized by using specific transmission radius of nodes. Moreover, Olariu and Stojmenović [5] have also proposed that adding more nodes to the areas with heavier traffic is a natural way to mitigate the energy hole problem, thus creating different node densities in different areas. This is also the basis of the network model in SNAA.Lian et al. [18] propose a nonuniform node distribution strategy to increase the network data capacity. Additional nodes acting as pure relays are added to the network. A routing algorithm is also proposed in which some nodes sleep once in a while to save energy. However, it cannot achieve energy balance. Meanwhile in SNAA, an optimal sleep scheduling strategy is proposed, which could effectively save energy for nodes near the center and also mitigate the energy hole problem.


### 2.2. Achieving Energy Balance with the Help of Mobile Sink or Optimized Deployment

Recently, much research has also proven that the exploitation of mobile sinks could improve the performance of WSNs and mitigate the energy hole problem [19]. Di Francesco et al. [19] proposed that, due to the limited power of nodes, using one or more mobile sinks for data collection in WSNs is an effective method to solve the hotspot problem. Moreover, the number of dropped packets is reduced due to the movement of the mobile sink closer to the sensor nodes in the sensor field [20]. A type of data collection method with the help of multiple mobile sinks is proposed by Ren and Liang [21] which reduce not only the energy consumption of the whole network but also the transmission delay. In [22], path constrained sink mobility is used to improve the energy efficiency of single-hop sensor networks which may be infeasible due to the limits of the path location and communication power.Moreover, there is also considerable literature addressing various aspects of energy balancing problem in WSNs. Fan et al. [23] propose a type of deployment strategy with relay nodes to ensure energy balance. By computing the most proper transmission distance, several relay nodes are set between source nodes and the base station to achieve balance in the energy consumption of sensor nodes and relaying nodes. However, this strategy takes a considerable cost in time and cannot be applied in large scale networks; Fei [24] proposes a grid based network deployment algorithm. In this algorithm, each grid defines an inner node, which has the least distance from the grid center, as its cluster. Besides, it utilizes the gateway to gather the information in a cluster and then deliver it to the nearest cluster head. This deployment strategy owns the advantages for the convenience of information management and data fusion. But it should be noted that energy unbalance is also a key problem in this network.Besides optimizing deployment schemes, heterogeneous initial energy allocation and heterogeneous modulation modes are proposed by some literatures as well to solve energy hole problem. In a circular network, Soltan et al. [25] choose noncoherent BFSK with low complexity and high SNR for the nodes near the base station and coherent BPSK with high complexity and relative low SNR for the nodes far from the base station. But this method cannot achieve self-adaptation in a varied network. What is more, heterogeneous modulation causes low transmission efficiency. In [26], Giridhar and Kumar also formulate the maximization of the network lifetime as a linear programming problem. They derive the lifetime bounds of WSNs with two regular topologies, namely, linear and two-dimensional networks. They conclude that simply transmitting data to the nearest neighbors can achieve near-optimal network lifetime asymptotically. Thus, in SNAA, each node transmits data to the optimal parent node according to their distance and the residual energy of the parent, which effectively reduce energy consumption on data uploading.


### 2.3. Mitigating the Energy Hole Problem in Circular Network

Ren et al. [27] propose a distance-based energy efficient placement in circular networks. Though coverage has been taken into consideration in this deployment, it fails to analyze the energy consumption on the condition of data fusion. In addition, [2, 4, 5] provide a similar method in which circular networks are to be divided into several annuluses with different radius. By utilizing the method to figure out the minimum value of the objective function, it is easy to get the optimum radius for each annulus. However, it also ignores the network coverage problem. In [28], the circular network is divided into subfields by first dividing the network into coronas and then further dividing the coronas into sectors. This logical division of network could reduce the probability of emergence of energy hole. However, within subfields, nodes suffer long distance communication when their CHs are at the other end.Wu et al. [29] proposed that, in a circular multihop sensor network (modeled as concentric coronas) with nonuniform node distribution and constant data reporting, the unbalanced energy depletion among all the nodes in the network is unavoidable. This is due to the intrinsic many-to-one traffic pattern of WSNs [29]. Nevertheless, nearly balanced energy depletion in the network is possible if the number of nodes increases in geometric progression from the outer coronas to the inner ones except the outermost one [29]. Therefore, Wu et al. [29] proposed a type of nonuniform node distribution strategy to achieve nearly balanced energy consumption in the network. A fixed ratio about the number of nodes in the two adjacent annuluses is adopted and a distributed shortest path routing algorithm is tailored for this nonuniform node distribution strategy.Based on the above researches and taking a real physical environment into account, a type of nonuniform node distribution strategy is proposed in this paper to mitigate the energy hole problem in WSNs. The contributions of this paper can be concluded as follows.Firstly, with the help of the nonuniform deployment strategy, the number of nodes increases from the outer annuluses to the inner ones. It could not only reduce the work load on nodes near the center but also mitigate the energy hole problem in circular network.Secondly, nodes in the two adjacent annuluses are synchronous during their transmitting and receiving phases which enhances the bandwidth utilization as well as the efficiency of data collection.Finally, as for nodes in idle listening mode, a type of sleep scheduling strategy is adopted to further reduce its energy consumption. In addition, more and more nodes in the same annulus could be as the relay which could effectively avoid the hotspot phenomenon.The remainder of this paper is organized as follows: the related works as well as the virtual annulus based network model are described in Sections2 and 3, respectively. In Section 4, synchronization of nodes in adjacent annuluses and the sleep scheduling strategy are described in detail. Experimental results of SNAA are shown in Section 5 and the conclusion is provided in the last section.


## 2.1. Nonuniform Node Distribution Strategy for Mitigating the Energy Hole Problem

Li and Mohapatra [16] present the first mathematical model towards the characterization of the energy hole problem. They consider sensor nodes distributed following the URP (Uniform Random Placement) law in a circular region divided into concentric coronas. They observe the impact of the following four factors on the energy hole problem: node density, hierarchical deployment, source bit rate, and traffic compression. They show that simply adding more nodes to the network does not solve the problem. By computing network lifetime after deployment, Hou et al. [17] adjust the location of relay nodes to maximize the network lifetime. But this method takes a heavy cost for the process of iteration and cannot adapt itself to varied networks.Liu et al. [4] proposed that node density should be proportional to the distance from sink. They formulated algorithms for deployment of nodes to achieve application required first node die time (FDT) and all nodes die time (ADT). Furthermore, they also proved that network lifetime can be maximized by using specific transmission radius of nodes. Moreover, Olariu and Stojmenović [5] have also proposed that adding more nodes to the areas with heavier traffic is a natural way to mitigate the energy hole problem, thus creating different node densities in different areas. This is also the basis of the network model in SNAA.Lian et al. [18] propose a nonuniform node distribution strategy to increase the network data capacity. Additional nodes acting as pure relays are added to the network. A routing algorithm is also proposed in which some nodes sleep once in a while to save energy. However, it cannot achieve energy balance. Meanwhile in SNAA, an optimal sleep scheduling strategy is proposed, which could effectively save energy for nodes near the center and also mitigate the energy hole problem.


## 2.2. Achieving Energy Balance with the Help of Mobile Sink or Optimized Deployment

Recently, much research has also proven that the exploitation of mobile sinks could improve the performance of WSNs and mitigate the energy hole problem [19]. Di Francesco et al. [19] proposed that, due to the limited power of nodes, using one or more mobile sinks for data collection in WSNs is an effective method to solve the hotspot problem. Moreover, the number of dropped packets is reduced due to the movement of the mobile sink closer to the sensor nodes in the sensor field [20]. A type of data collection method with the help of multiple mobile sinks is proposed by Ren and Liang [21] which reduce not only the energy consumption of the whole network but also the transmission delay. In [22], path constrained sink mobility is used to improve the energy efficiency of single-hop sensor networks which may be infeasible due to the limits of the path location and communication power.Moreover, there is also considerable literature addressing various aspects of energy balancing problem in WSNs. Fan et al. [23] propose a type of deployment strategy with relay nodes to ensure energy balance. By computing the most proper transmission distance, several relay nodes are set between source nodes and the base station to achieve balance in the energy consumption of sensor nodes and relaying nodes. However, this strategy takes a considerable cost in time and cannot be applied in large scale networks; Fei [24] proposes a grid based network deployment algorithm. In this algorithm, each grid defines an inner node, which has the least distance from the grid center, as its cluster. Besides, it utilizes the gateway to gather the information in a cluster and then deliver it to the nearest cluster head. This deployment strategy owns the advantages for the convenience of information management and data fusion. But it should be noted that energy unbalance is also a key problem in this network.Besides optimizing deployment schemes, heterogeneous initial energy allocation and heterogeneous modulation modes are proposed by some literatures as well to solve energy hole problem. In a circular network, Soltan et al. [25] choose noncoherent BFSK with low complexity and high SNR for the nodes near the base station and coherent BPSK with high complexity and relative low SNR for the nodes far from the base station. But this method cannot achieve self-adaptation in a varied network. What is more, heterogeneous modulation causes low transmission efficiency. In [26], Giridhar and Kumar also formulate the maximization of the network lifetime as a linear programming problem. They derive the lifetime bounds of WSNs with two regular topologies, namely, linear and two-dimensional networks. They conclude that simply transmitting data to the nearest neighbors can achieve near-optimal network lifetime asymptotically. Thus, in SNAA, each node transmits data to the optimal parent node according to their distance and the residual energy of the parent, which effectively reduce energy consumption on data uploading.


## 2.3. Mitigating the Energy Hole Problem in Circular Network

Ren et al. [27] propose a distance-based energy efficient placement in circular networks. Though coverage has been taken into consideration in this deployment, it fails to analyze the energy consumption on the condition of data fusion. In addition, [2, 4, 5] provide a similar method in which circular networks are to be divided into several annuluses with different radius. By utilizing the method to figure out the minimum value of the objective function, it is easy to get the optimum radius for each annulus. However, it also ignores the network coverage problem. In [28], the circular network is divided into subfields by first dividing the network into coronas and then further dividing the coronas into sectors. This logical division of network could reduce the probability of emergence of energy hole. However, within subfields, nodes suffer long distance communication when their CHs are at the other end.Wu et al. [29] proposed that, in a circular multihop sensor network (modeled as concentric coronas) with nonuniform node distribution and constant data reporting, the unbalanced energy depletion among all the nodes in the network is unavoidable. This is due to the intrinsic many-to-one traffic pattern of WSNs [29]. Nevertheless, nearly balanced energy depletion in the network is possible if the number of nodes increases in geometric progression from the outer coronas to the inner ones except the outermost one [29]. Therefore, Wu et al. [29] proposed a type of nonuniform node distribution strategy to achieve nearly balanced energy consumption in the network. A fixed ratio about the number of nodes in the two adjacent annuluses is adopted and a distributed shortest path routing algorithm is tailored for this nonuniform node distribution strategy.Based on the above researches and taking a real physical environment into account, a type of nonuniform node distribution strategy is proposed in this paper to mitigate the energy hole problem in WSNs. The contributions of this paper can be concluded as follows.Firstly, with the help of the nonuniform deployment strategy, the number of nodes increases from the outer annuluses to the inner ones. It could not only reduce the work load on nodes near the center but also mitigate the energy hole problem in circular network.Secondly, nodes in the two adjacent annuluses are synchronous during their transmitting and receiving phases which enhances the bandwidth utilization as well as the efficiency of data collection.Finally, as for nodes in idle listening mode, a type of sleep scheduling strategy is adopted to further reduce its energy consumption. In addition, more and more nodes in the same annulus could be as the relay which could effectively avoid the hotspot phenomenon.The remainder of this paper is organized as follows: the related works as well as the virtual annulus based network model are described in Sections2 and 3, respectively. In Section 4, synchronization of nodes in adjacent annuluses and the sleep scheduling strategy are described in detail. Experimental results of SNAA are shown in Section 5 and the conclusion is provided in the last section.


## 3. Network Model

As mentioned above, the sink-based data gathering method is widely used in WSNs [1–6]. Similar to [4, 29], network in this paper is defined as a circular area with a radius R, while the static sink node is deployed at the center O, whose coordinate is (0,0). In addition, the total number of nodes is n and the coordinate of each node Si is defined as (Xi,Yi).Without loss of generality, the energy consumption model of nodes in SNAA is the same as [14], as shown in Figure 1. Both the free space and the multipath fading channel models were used, depending on the distance between the transmitter and receiver [14].Figure 1
Radio energy dissipation model in WSNs [14].In formulas (1) and (2), Esend and Erec are the energy consumption of one node during its sending and receiving phase, respectively, while Eelec is the unit energy consumption of the circuit. εfs and εamp are the constant parameters of the signal amplifier in the free space and multipath fading environment, and d0=εfs/εamp denotes the threshold distance.To transmit ac-bit message for a distance d, the radio expends(1)Esendc,d=cEelec+cεfsd2,d<d0,cEelec+cεampd4,d≥d0,and, to receive this message, the radio expends(2)Erecc=cEelec.


### 3.1. Single-Hop Data Transmission Mode

In this mode, each nodeSi(i=1,2,…,n) uploads its data to the sink within one hop and the Euclidean Distance between them is dio, as shown in Figure 2. Thus, energy consumption of Si in a round of transmission is(3)ESi=ciEelec+ε′diok.Figure 2
Circular network in single-hop data transmission mode.In (3), ci is the amount of data collected by Si in one round, and(4)ε′=εfs,ifdio<d0,εamp,ifdio≥d0.Thus, total energy consumption of all nodes in a single round could be expressed as(5)Etotal=∑i=1nESi=∑i=1nciEelec+μ′diok.It is assumed that nodes in the network have been randomly deployed with a uniform distribution. So,(6)fx,y=1πR2,x2+y2≤R2,0,x2+y2>R2.Therefore, the expectation distance between the node and sink in single-hop data transmission mode is(7)Ed=∑i=1ndiopi=∫0Rx2πxπR2dx=23R.Thus,(8)Etotal=∑i=1nciEelec+μ′23Rk.Therefore, the single-hop data transmission mode is only suitable for the network with small radius and less nodes.


### 3.2. Multihop Data Transmission Mode in WSNs

Since the limitation of the transmission distance of one node, the cluster-based topology is widely used in large scale deployed sensor networks. Similar to [4, 29], the circular network is divided into N virtual concentric annuluses with the same width dw, as shown in Figure 3. Node in the jth annulus uploads its data to the parent in the (j-1)th annulus in one hop. Thus, total energy consumption of all nodes in a single round could be expressed as(9)Etotal=EN+EN-1+⋯+E1+N-1EN,N-1+N-2EN-1,N-2+⋯+2E3,2+E2,1.Figure 3
Circular network in multihop data transmission mode.In formula (9), Ej is the energy consumption on data transmission from nodes in the jth annulus to the nodes in the (j-1)th one, while total energy consumption on receiving data from the jth annulus as well as transmitting data from the (j-1)th annulus to the (j-2)th one is defined as Ej,j-1 (without data fusion). Thus, it is known that(10)Ej=∑i=1NumjESi=∑i=1NumjciEelec+ε′dj,j-1k.In a uniformly distributed network, the total number of nodes in the jth annulus is(11)Numj=nπjdw2-πj-1dw2πNdw2=n2j-1N2.Therefore, the expectation value of the single-hop communication distance between nodes in the adjacent annuluses is(12)Edj,j-1=∑i=1jdi,i-1pi=∫j-1dwjdw2πxx-j-1dwπjdw2-j-1dw2dx=3j-16j-3dw.So formula (10) can be further expressed as(13)Ej=∑i=1NumjciEelec+ε′3j-16j-3dwk.Similarly,(14)Ej,j-1=∑i=1Numjci2Eelec+ε′dj-1,j-2k.It is easy to know that data generated in thejth annulus could be transmitted to sink after j-1 hops. Therefore, the energy consumption on data transmission is (j-1)Ej,j-1. For simplicity, the amount of data collected by each node in one round of data gathering time is defined as c. Therefore, total energy consumption of the whole network on communication can be expressed as follows:(15)Etotal=∑j=1Ncj2-j-12N2nEelec+ε′3j-16j-3dwk+∑j=2Nj-1cj2-j-12N2n2Eelec+ε′dj-1,j-2k.Thus, in a multihop sensor network, energy consumption on data transmission is related to the number of nodes, the number of hops, and the single-hop communication distance.On the other hand, in a multihop circular network, nodes in the inner annulus near the sink consume more energy on data receiving and transmitting [10–12]. Furthermore, as known from formula (11), in a uniform distributed sensor network, the value of Numj is inversely proportional to j, which further increases the burden of the nodes close to sink and could easily cause energy hole problem. To balance energy consumption in SNAA, the circular network is also divided into N virtual concentric annuluses with the same width dw and the number of nodes in each annulus could be calculated by formula (16). q is the ratio of the number of nodes in two adjacent annuluses, while δ is an adjustable parameter in 0~1. The network deployment model is shown in Figure 4  (q=1.2, δ=0.8):(16)Numj-1Numj=q,j∈2,N-1,δq,j=N.Figure 4
Node deployment model in SNAA.Thus, from the(N-1)th virtual annulus to the inner one, the value of Numj increases with the decrease of j. This ensures that much more nodes around the sink could participate in data forwarding and uploading, which effectively balances the energy consumption.


## 3.1. Single-Hop Data Transmission Mode

In this mode, each nodeSi(i=1,2,…,n) uploads its data to the sink within one hop and the Euclidean Distance between them is dio, as shown in Figure 2. Thus, energy consumption of Si in a round of transmission is(3)ESi=ciEelec+ε′diok.Figure 2
Circular network in single-hop data transmission mode.In (3), ci is the amount of data collected by Si in one round, and(4)ε′=εfs,ifdio<d0,εamp,ifdio≥d0.Thus, total energy consumption of all nodes in a single round could be expressed as(5)Etotal=∑i=1nESi=∑i=1nciEelec+μ′diok.It is assumed that nodes in the network have been randomly deployed with a uniform distribution. So,(6)fx,y=1πR2,x2+y2≤R2,0,x2+y2>R2.Therefore, the expectation distance between the node and sink in single-hop data transmission mode is(7)Ed=∑i=1ndiopi=∫0Rx2πxπR2dx=23R.Thus,(8)Etotal=∑i=1nciEelec+μ′23Rk.Therefore, the single-hop data transmission mode is only suitable for the network with small radius and less nodes.


## 3.2. Multihop Data Transmission Mode in WSNs

Since the limitation of the transmission distance of one node, the cluster-based topology is widely used in large scale deployed sensor networks. Similar to [4, 29], the circular network is divided into N virtual concentric annuluses with the same width dw, as shown in Figure 3. Node in the jth annulus uploads its data to the parent in the (j-1)th annulus in one hop. Thus, total energy consumption of all nodes in a single round could be expressed as(9)Etotal=EN+EN-1+⋯+E1+N-1EN,N-1+N-2EN-1,N-2+⋯+2E3,2+E2,1.Figure 3
Circular network in multihop data transmission mode.In formula (9), Ej is the energy consumption on data transmission from nodes in the jth annulus to the nodes in the (j-1)th one, while total energy consumption on receiving data from the jth annulus as well as transmitting data from the (j-1)th annulus to the (j-2)th one is defined as Ej,j-1 (without data fusion). Thus, it is known that(10)Ej=∑i=1NumjESi=∑i=1NumjciEelec+ε′dj,j-1k.In a uniformly distributed network, the total number of nodes in the jth annulus is(11)Numj=nπjdw2-πj-1dw2πNdw2=n2j-1N2.Therefore, the expectation value of the single-hop communication distance between nodes in the adjacent annuluses is(12)Edj,j-1=∑i=1jdi,i-1pi=∫j-1dwjdw2πxx-j-1dwπjdw2-j-1dw2dx=3j-16j-3dw.So formula (10) can be further expressed as(13)Ej=∑i=1NumjciEelec+ε′3j-16j-3dwk.Similarly,(14)Ej,j-1=∑i=1Numjci2Eelec+ε′dj-1,j-2k.It is easy to know that data generated in thejth annulus could be transmitted to sink after j-1 hops. Therefore, the energy consumption on data transmission is (j-1)Ej,j-1. For simplicity, the amount of data collected by each node in one round of data gathering time is defined as c. Therefore, total energy consumption of the whole network on communication can be expressed as follows:(15)Etotal=∑j=1Ncj2-j-12N2nEelec+ε′3j-16j-3dwk+∑j=2Nj-1cj2-j-12N2n2Eelec+ε′dj-1,j-2k.Thus, in a multihop sensor network, energy consumption on data transmission is related to the number of nodes, the number of hops, and the single-hop communication distance.On the other hand, in a multihop circular network, nodes in the inner annulus near the sink consume more energy on data receiving and transmitting [10–12]. Furthermore, as known from formula (11), in a uniform distributed sensor network, the value of Numj is inversely proportional to j, which further increases the burden of the nodes close to sink and could easily cause energy hole problem. To balance energy consumption in SNAA, the circular network is also divided into N virtual concentric annuluses with the same width dw and the number of nodes in each annulus could be calculated by formula (16). q is the ratio of the number of nodes in two adjacent annuluses, while δ is an adjustable parameter in 0~1. The network deployment model is shown in Figure 4  (q=1.2, δ=0.8):(16)Numj-1Numj=q,j∈2,N-1,δq,j=N.Figure 4
Node deployment model in SNAA.Thus, from the(N-1)th virtual annulus to the inner one, the value of Numj increases with the decrease of j. This ensures that much more nodes around the sink could participate in data forwarding and uploading, which effectively balances the energy consumption.


## 4. Method Description

### 4.1. Optimal Parent Node Selection

In order to reduce the high load on relay nodes in a cluster-based sensor network and also to mitigate the energy hole problem, some definitions are described as follows.Definition 1 (the optimal hop distanced(Si)hop).
According to the above analysis, it is known that, in SNAA, node in thejth annulus only needs to communicate with one node in the (j-1)th annulus. In addition, d(Si)hop is defined as the Euclidean Distance between Si and Pi. Si is just the sensor node in the jth annulus while Pi is the intersection point of segment SiO and the inner boundary of the (j-1)th annulus (j>2), as shown in Figure 4. When j=1 or j=2, Pi is just point O. Thus,(17)dSihop=Xi2+Yi2-j-2dw,j>2,Xi2+Yi2,j∈1,2.Definition 2 (region for candidate parent nodes).
To reduce the communication cost on parent finding, a virtual circle about nodeSi is introduced, as shown in Figure 4. Si is the center of the circle and d(Si)hop is its radius. The region consisting of the arc of the virtual circle as well as the outer boundary of the (j-1)th annulus is defined as the “region for candidate parent nodes of Si” (“candidate region” for short), as the shadow area shown in Figure 4. The parent node of Si will be selected in the candidate region. Therefore, it is unnecessary for Si to communicate with other nodes with the maximum power. Si only need to transmit its data to a distance of d(Si)hop.According to the energy consumption model of nodes in [14], it is known that the communication cost of Si per unit time on transmitting one bit of data to the distance of dmax (defined as the maximum distance, the data could be transmitted in one hop) and d(Si)hop (shown as emax and e, resp.) could be expressed as follows:(18)emaxe=kEelec+kεampdmax4kEelec+kεfsdSihop2.According to [14], d0=εfs/εamp=10/0.013≈87.7 m, while the value of dmax is usually regarded as 100 m. So, in (18), emax has a linear relationship with dmax4. In addition, according to the network topology of SNAA, it is known that Max(dSihop)=2dw. Thus, the value of dw should be less than 43.85 m in our algorithm.Moreover, in (18), Eelec = 50 nJ × b−1, μfs=10 pJ × (b/m2)−1, and μamp=0.0013 pJ × (b/m2)−1 [4]. For easy calculation, let dmax=jdw and dSihop=2dw. Thus, formula (18) could be expressed as (19)emaxe=5×104+10j4dw25×104+0.0052.So SNAA could effectively reduce energy consumption on communication, especially for the high value ofj and dw. In addition, Wb is the weight of node Sb in the candidate region and its value is defined as follows:(20)Wb=αErSb+βdib+γCSb.E
r
(
S
b
) is the residual energy of Sb, while dib is the distance between Si and Sb. C(Sb) is the number of times about Sb being selected as the relay node of Si. α, β, and γ are the adjustable parameters which satisfy α+β+γ=1. In a round of data gathering time, the node with the maximum value of Wb will be selected as the parent of Si. The pseudocode about the parent node selection strategy is shown in Algorithm 1 and the definition of each function is described as follows:OptDistance(Si): return the optimal hop distance of S.CandiRegion(d): return the candidate region of Si.Weight(): return the weight of the candidate parent node.Sleep(): go into sleeping mode.Receive(): return the amount of data received by node.Collect(): return the amount of data collected by node.Transmit(data): transmit data.Algorithm 1:Optimal parent node selection algorithm.
(01)Input:Si(Xi,Yi), OptNode = Null
(02)  d(Si)hop = OptDistance(Si(Xi,Yi))
(03) for each nodeSjinCandiRegion(d(Si)hop)
(04) OptNode =Max⁡(Sj.Weight());
(05)if(OptNode == Null)
(06) Si(Xi,Yi).Sleep()
(07)else
(08) if(OptNode.Receive() != 0)
(09)Transmit(OptNode.Receive() + OptNode.Collect())
(10)else
(11)Transmit(OptNode.Collect())
(12)endif
(13)endifFurthermore, the size of the candidate region is related to the probability of nodes to find their parent. In Figure5, the area of Si’s candidate region could be expressed as(21)SiC=πdoa22θ2π-12doa2sin⁡2θ+πdia22ω2π-12dia2sin⁡2ω=j-12dw2θ-12sin⁡2θ+dSihopω-12sin⁡2ω.Figure 5
Analysis about the deployment of nodes.From the definition ofdSihop, it is known that(22)dw<dSihop≤2dw.Therefore, the location of Si and the value of dw are the main factors that determine the size of Si(C).WhenSi is located at the outer boundary of the jth annulus, the size of its candidate region has the maximum value, as S8 shows in Figure 5. On the contrary, when Si is just at the inner boundary of the jth annulus, the area of its candidate region is the smallest one, as S9 shows. So the minimum size of the candidate region in SNAA could be approximately considered as 0.5πdw2, while the area of the (j-1)th virtual annulus is(23)Sj=πj-1dw2-πj-2dw2=πdw22j-3.Thus, in the case of uniform distribution, when the value ofNumj satisfies formula (24), there is at least one candidate node for Si in the candidate region. In SNAA, it is known that the number of nodes increases from the outer annulus to the inner one. So it only needs to ensure that NumN is not less than 4N-6:(24)Numj≥πdw22j-30.5πdw2=4j-6.


### 4.2. Data Uploading Strategy Based on Synchronization of Nodes in Adjacent Annuluses

As mentioned before, in the cluster-tree based network, the burdens on the relay nodes as well as the sink are obviously higher than the leaf nodes. Therefore, the “hotspots” may appear in the center of the network. In addition, cooperation between nodes is more and more important during the data transmitting and receiving phases. Thus, a type of data uploading strategy based on synchronization of nodes is proposed as follows.T is defined as one round of execution time in SNAA. Ts, Tt, and Tr are the time spending on sampling, transmitting, and receiving, respectively, and T=Ts+Tt+Tr. Data uploading process of nodes in adjacent annuluses is shown in Figure 6.Figure 6
Working flowchart of nodes in data uploading phase.At the beginning of each round, all the nodes in the network continue sampling inTs with a fixed rate u. Then each node in the (N-2k)th virtual annulus selects one active node with the maximum value of Wb in the candidate region as its parent. k is a nonnegative integer and k∈0,N/2-1. Thus, the network topology is shown in Figure 7.Figure 7
Network topology inTt.Nodes in the(N-2k)th annulus then send data to their parent nodes in the adjacent inner annulus in Tt. Moreover, in SNAA, the number of nodes increases from the outer annulus to the inner one. Therefore, a sleeping scheduling strategy is used to further save energy about nodes near the sink. The grey nodes in Figure 7 are the sleeping nodes and the sleeping scheduling strategy is described in Section 4.3. Thus, node Si in the (N-2k)th annulus may not find its parent node because there are no active nodes in the candidate region, as S1 and S2 show in Figure 7. In this case, Si goes into sleeping mode in Tt and the nodes which are not selected as the parent could also bring in sleeping mode in the same period, as S3 and S4 show in Figure 7.Similarly, at the end ofTt, Si′ in the (N-2k-1)th annulus will select one node with the maximum value Wb in the candidate region as its parent. If there are no active nodes in the region, Si′ goes into sleeping mode during the next period Tr to save energy. Moreover, nodes which are not selected as the parent could also bring in sleeping mode in Tr, as S5 shows in Figure 8. Topology in this case is shown in Figure 8, in which the dotted lines are just the communication links from the (N-2k-1)th annulus to the (N-2k-2)th one. In addition, nodes in the Nth annulus need not receive any data in Tr, so they could also sleep in this period, as S1, S6, and S7 show in Figure 8.Figure 8
Network topology inTr.From the analysis above, it is well known that, after one-round time ofT, data generated in the jth annulus (including data sensed by nodes in this annulus and data received from the outer annuluses) could be transmitted to the nodes in the (j-2)th annulus. Thus, in SNAA, nodes in the adjacent annuluses communicate with each other synchronously, which not only enhances the efficiency of data gathering, but also reduces energy consumption on communication.


### 4.3. Discussion about Node Sleeping in SNAA

As mentioned in Section4.2, nodes which could not be selected as the parent or nodes that have no next-hop neighbors go into sleeping mode in SNAA, while in WSNs, since the existence of energy consumption on state switching, quantitative analysis should be considered to determine the working statement of nodes. As shown in Figure 9, Pm, Pl, and Pd are the power consumption on idle listening, light sleeping, and deep sleeping, respectively. Pl′ is defined as the power consumption on state switching between listening and light sleeping state while the time spent on this switching is tl. Similarly, Pd′ is the power consumption on state switching between listening and deep sleeping state, and td is the switching time. In general, Pm≫Pl>Pd, td>tl, and Pd′>Pl′ [10, 11].Figure 9
Power consumption under different working modes.Thus, energy consumption of nodeSi in T′ could be expressed as follows:(25)ET′=PmT′,activemode,2tlPl′+T′-2tlPl,lightsleepingmode,2tdPd′+T′-2tdPd,deepsleepingmode.In addition,T1 and T2 are defined in (26)T1=2tlPl′-PlPm-Pl,T2=2tdPd′-Pd+2tlPl-Pl′Pl-Pd.It is not difficult to know that when0<T′<T1, keep Si in active mode during T′ which could save more energy, while if T1≤T′<T2, Si should go into light sleeping mode and when T′≥T2, being in deep sleeping mode is the best choice for Si, as shown in Figure 10.Figure 10
Mode selection forSi.On the other hand, to further mitigate the energy hole problem, all the nodes in the network should check their residual energyEr at the end of each round. If Er/Er′<χ and T1≤T, the node will go into sleeping mode during the next round time. Er′ is the residual energy of node at the end of the last T, and χ is an adjustable parameter.


### 4.4. Discussion about the Value ofT in SNAA

As mentioned before, in SNAA,T=Ts+Tt+Tr. Therefore, the value of T is important for the efficiency of the synchronous communication between nodes in adjacent annuluses. SN, which collects c-bit data in T, is assumed to be the node in the Nth annulus. Without considering data fusion, these c-bit data will be uploaded to node SN-2 in the (N-2)th annulus at the end of this T and then be transmitted to node SN-4 in the (N-4)th annulus at the end of the next T, and so forth. In this transmission path, each node could generate c-bit data per round. Therefore, when the data generated from SN finally arrive at the sink, there are also (N-1)c-bit data being received by sink from this path. In addition, the time spent on transmitting their Nc-bit data to sink could be expressed as follows:(27)TN=N+12T.However, in SNAA, owing to the sleep scheduling strategy, it may not ensure that each node could upload data to its parent during one period ofT. In the worst case, in a transmission path from the node in the Nth annulus to sink, data will be temporarily stored in each node for the time of T. Meanwhile, during this time, the node could also generate c-bit data. Thus, the possible maximum amount of data uploaded from one node in the jth annulus to its parent in the (j-1)th one in one round of time is (2+3(N-j))cbits. Therefore, as for the sink node, this value is (2+3(N-1))cbits and the value of T(N) in this case is NT. vt is the data transmission speed in SNAA; thus, it is easy to know that each active node could accomplish its data receiving and transmitting tasks in T if and only if(28)Tt=Tr=2+3N-1cvt.Moreover, it is known that c=Ts×u. Therefore, Ts, Tt, and Tr should satisfy(29)Ts:Tt:Tr=vt2+3N-1u:1:1.It is obvious that when N is small, the value of Ts is higher than Tt and Tr. Therefore, if the network has heavy sensing task, the value of N should be low to achieve energy balance. On the contrary, with the increase of N, either Tt or Tr will be larger than Ts. According to (26), more and more nodes without the transmitting or receiving task may go into light sleeping or deep sleeping mode in this case, which effectively mitigate the energy hole problem.


## 4.1. Optimal Parent Node Selection

In order to reduce the high load on relay nodes in a cluster-based sensor network and also to mitigate the energy hole problem, some definitions are described as follows.Definition 1 (the optimal hop distanced(Si)hop).
According to the above analysis, it is known that, in SNAA, node in thejth annulus only needs to communicate with one node in the (j-1)th annulus. In addition, d(Si)hop is defined as the Euclidean Distance between Si and Pi. Si is just the sensor node in the jth annulus while Pi is the intersection point of segment SiO and the inner boundary of the (j-1)th annulus (j>2), as shown in Figure 4. When j=1 or j=2, Pi is just point O. Thus,(17)dSihop=Xi2+Yi2-j-2dw,j>2,Xi2+Yi2,j∈1,2.Definition 2 (region for candidate parent nodes).
To reduce the communication cost on parent finding, a virtual circle about nodeSi is introduced, as shown in Figure 4. Si is the center of the circle and d(Si)hop is its radius. The region consisting of the arc of the virtual circle as well as the outer boundary of the (j-1)th annulus is defined as the “region for candidate parent nodes of Si” (“candidate region” for short), as the shadow area shown in Figure 4. The parent node of Si will be selected in the candidate region. Therefore, it is unnecessary for Si to communicate with other nodes with the maximum power. Si only need to transmit its data to a distance of d(Si)hop.According to the energy consumption model of nodes in [14], it is known that the communication cost of Si per unit time on transmitting one bit of data to the distance of dmax (defined as the maximum distance, the data could be transmitted in one hop) and d(Si)hop (shown as emax and e, resp.) could be expressed as follows:(18)emaxe=kEelec+kεampdmax4kEelec+kεfsdSihop2.According to [14], d0=εfs/εamp=10/0.013≈87.7 m, while the value of dmax is usually regarded as 100 m. So, in (18), emax has a linear relationship with dmax4. In addition, according to the network topology of SNAA, it is known that Max(dSihop)=2dw. Thus, the value of dw should be less than 43.85 m in our algorithm.Moreover, in (18), Eelec = 50 nJ × b−1, μfs=10 pJ × (b/m2)−1, and μamp=0.0013 pJ × (b/m2)−1 [4]. For easy calculation, let dmax=jdw and dSihop=2dw. Thus, formula (18) could be expressed as (19)emaxe=5×104+10j4dw25×104+0.0052.So SNAA could effectively reduce energy consumption on communication, especially for the high value ofj and dw. In addition, Wb is the weight of node Sb in the candidate region and its value is defined as follows:(20)Wb=αErSb+βdib+γCSb.E
r
(
S
b
) is the residual energy of Sb, while dib is the distance between Si and Sb. C(Sb) is the number of times about Sb being selected as the relay node of Si. α, β, and γ are the adjustable parameters which satisfy α+β+γ=1. In a round of data gathering time, the node with the maximum value of Wb will be selected as the parent of Si. The pseudocode about the parent node selection strategy is shown in Algorithm 1 and the definition of each function is described as follows:OptDistance(Si): return the optimal hop distance of S.CandiRegion(d): return the candidate region of Si.Weight(): return the weight of the candidate parent node.Sleep(): go into sleeping mode.Receive(): return the amount of data received by node.Collect(): return the amount of data collected by node.Transmit(data): transmit data.Algorithm 1:Optimal parent node selection algorithm.
(01)Input:Si(Xi,Yi), OptNode = Null
(02)  d(Si)hop = OptDistance(Si(Xi,Yi))
(03) for each nodeSjinCandiRegion(d(Si)hop)
(04) OptNode =Max⁡(Sj.Weight());
(05)if(OptNode == Null)
(06) Si(Xi,Yi).Sleep()
(07)else
(08) if(OptNode.Receive() != 0)
(09)Transmit(OptNode.Receive() + OptNode.Collect())
(10)else
(11)Transmit(OptNode.Collect())
(12)endif
(13)endifFurthermore, the size of the candidate region is related to the probability of nodes to find their parent. In Figure5, the area of Si’s candidate region could be expressed as(21)SiC=πdoa22θ2π-12doa2sin⁡2θ+πdia22ω2π-12dia2sin⁡2ω=j-12dw2θ-12sin⁡2θ+dSihopω-12sin⁡2ω.Figure 5
Analysis about the deployment of nodes.From the definition ofdSihop, it is known that(22)dw<dSihop≤2dw.Therefore, the location of Si and the value of dw are the main factors that determine the size of Si(C).WhenSi is located at the outer boundary of the jth annulus, the size of its candidate region has the maximum value, as S8 shows in Figure 5. On the contrary, when Si is just at the inner boundary of the jth annulus, the area of its candidate region is the smallest one, as S9 shows. So the minimum size of the candidate region in SNAA could be approximately considered as 0.5πdw2, while the area of the (j-1)th virtual annulus is(23)Sj=πj-1dw2-πj-2dw2=πdw22j-3.Thus, in the case of uniform distribution, when the value ofNumj satisfies formula (24), there is at least one candidate node for Si in the candidate region. In SNAA, it is known that the number of nodes increases from the outer annulus to the inner one. So it only needs to ensure that NumN is not less than 4N-6:(24)Numj≥πdw22j-30.5πdw2=4j-6.


## 4.2. Data Uploading Strategy Based on Synchronization of Nodes in Adjacent Annuluses

As mentioned before, in the cluster-tree based network, the burdens on the relay nodes as well as the sink are obviously higher than the leaf nodes. Therefore, the “hotspots” may appear in the center of the network. In addition, cooperation between nodes is more and more important during the data transmitting and receiving phases. Thus, a type of data uploading strategy based on synchronization of nodes is proposed as follows.T is defined as one round of execution time in SNAA. Ts, Tt, and Tr are the time spending on sampling, transmitting, and receiving, respectively, and T=Ts+Tt+Tr. Data uploading process of nodes in adjacent annuluses is shown in Figure 6.Figure 6
Working flowchart of nodes in data uploading phase.At the beginning of each round, all the nodes in the network continue sampling inTs with a fixed rate u. Then each node in the (N-2k)th virtual annulus selects one active node with the maximum value of Wb in the candidate region as its parent. k is a nonnegative integer and k∈0,N/2-1. Thus, the network topology is shown in Figure 7.Figure 7
Network topology inTt.Nodes in the(N-2k)th annulus then send data to their parent nodes in the adjacent inner annulus in Tt. Moreover, in SNAA, the number of nodes increases from the outer annulus to the inner one. Therefore, a sleeping scheduling strategy is used to further save energy about nodes near the sink. The grey nodes in Figure 7 are the sleeping nodes and the sleeping scheduling strategy is described in Section 4.3. Thus, node Si in the (N-2k)th annulus may not find its parent node because there are no active nodes in the candidate region, as S1 and S2 show in Figure 7. In this case, Si goes into sleeping mode in Tt and the nodes which are not selected as the parent could also bring in sleeping mode in the same period, as S3 and S4 show in Figure 7.Similarly, at the end ofTt, Si′ in the (N-2k-1)th annulus will select one node with the maximum value Wb in the candidate region as its parent. If there are no active nodes in the region, Si′ goes into sleeping mode during the next period Tr to save energy. Moreover, nodes which are not selected as the parent could also bring in sleeping mode in Tr, as S5 shows in Figure 8. Topology in this case is shown in Figure 8, in which the dotted lines are just the communication links from the (N-2k-1)th annulus to the (N-2k-2)th one. In addition, nodes in the Nth annulus need not receive any data in Tr, so they could also sleep in this period, as S1, S6, and S7 show in Figure 8.Figure 8
Network topology inTr.From the analysis above, it is well known that, after one-round time ofT, data generated in the jth annulus (including data sensed by nodes in this annulus and data received from the outer annuluses) could be transmitted to the nodes in the (j-2)th annulus. Thus, in SNAA, nodes in the adjacent annuluses communicate with each other synchronously, which not only enhances the efficiency of data gathering, but also reduces energy consumption on communication.


## 4.3. Discussion about Node Sleeping in SNAA

As mentioned in Section4.2, nodes which could not be selected as the parent or nodes that have no next-hop neighbors go into sleeping mode in SNAA, while in WSNs, since the existence of energy consumption on state switching, quantitative analysis should be considered to determine the working statement of nodes. As shown in Figure 9, Pm, Pl, and Pd are the power consumption on idle listening, light sleeping, and deep sleeping, respectively. Pl′ is defined as the power consumption on state switching between listening and light sleeping state while the time spent on this switching is tl. Similarly, Pd′ is the power consumption on state switching between listening and deep sleeping state, and td is the switching time. In general, Pm≫Pl>Pd, td>tl, and Pd′>Pl′ [10, 11].Figure 9
Power consumption under different working modes.Thus, energy consumption of nodeSi in T′ could be expressed as follows:(25)ET′=PmT′,activemode,2tlPl′+T′-2tlPl,lightsleepingmode,2tdPd′+T′-2tdPd,deepsleepingmode.In addition,T1 and T2 are defined in (26)T1=2tlPl′-PlPm-Pl,T2=2tdPd′-Pd+2tlPl-Pl′Pl-Pd.It is not difficult to know that when0<T′<T1, keep Si in active mode during T′ which could save more energy, while if T1≤T′<T2, Si should go into light sleeping mode and when T′≥T2, being in deep sleeping mode is the best choice for Si, as shown in Figure 10.Figure 10
Mode selection forSi.On the other hand, to further mitigate the energy hole problem, all the nodes in the network should check their residual energyEr at the end of each round. If Er/Er′<χ and T1≤T, the node will go into sleeping mode during the next round time. Er′ is the residual energy of node at the end of the last T, and χ is an adjustable parameter.


## 4.4. Discussion about the Value ofT in SNAA

As mentioned before, in SNAA,T=Ts+Tt+Tr. Therefore, the value of T is important for the efficiency of the synchronous communication between nodes in adjacent annuluses. SN, which collects c-bit data in T, is assumed to be the node in the Nth annulus. Without considering data fusion, these c-bit data will be uploaded to node SN-2 in the (N-2)th annulus at the end of this T and then be transmitted to node SN-4 in the (N-4)th annulus at the end of the next T, and so forth. In this transmission path, each node could generate c-bit data per round. Therefore, when the data generated from SN finally arrive at the sink, there are also (N-1)c-bit data being received by sink from this path. In addition, the time spent on transmitting their Nc-bit data to sink could be expressed as follows:(27)TN=N+12T.However, in SNAA, owing to the sleep scheduling strategy, it may not ensure that each node could upload data to its parent during one period ofT. In the worst case, in a transmission path from the node in the Nth annulus to sink, data will be temporarily stored in each node for the time of T. Meanwhile, during this time, the node could also generate c-bit data. Thus, the possible maximum amount of data uploaded from one node in the jth annulus to its parent in the (j-1)th one in one round of time is (2+3(N-j))cbits. Therefore, as for the sink node, this value is (2+3(N-1))cbits and the value of T(N) in this case is NT. vt is the data transmission speed in SNAA; thus, it is easy to know that each active node could accomplish its data receiving and transmitting tasks in T if and only if(28)Tt=Tr=2+3N-1cvt.Moreover, it is known that c=Ts×u. Therefore, Ts, Tt, and Tr should satisfy(29)Ts:Tt:Tr=vt2+3N-1u:1:1.It is obvious that when N is small, the value of Ts is higher than Tt and Tr. Therefore, if the network has heavy sensing task, the value of N should be low to achieve energy balance. On the contrary, with the increase of N, either Tt or Tr will be larger than Ts. According to (26), more and more nodes without the transmitting or receiving task may go into light sleeping or deep sleeping mode in this case, which effectively mitigate the energy hole problem.


## 5. Experimental Results and Analysis

The performance of SNAA on energy balance, network lifetime, and the efficiency of data collection are analyzed with the help of Omnet++4.0 and Matlab 7.0. Furthermore, we compare SNAA with the geometric proportion deployment strategy proposed by Wu et al. [29] and the energy hole mitigating algorithm with the optimal width of annulus proposed by Liu et al. [4], respectively. Parameter values of this simulation are shown in Table 1.Table 1
Parameter values of simulation.
Parameter
Symbol
Value
Unit
Initial energy of node
E
0
100
J
Energy consumption of wireless sending and receiving circuit
E
e
l
e
c
50
nJ× b−1
Energy consumption of amplifier in free-space model
ε
f
s
10
pJ× (b/m2)−1
Energy consumption of amplifier in multipath fading model
ε
a
m
p
0.0013
pJ× (b/m4)−1
Width of the annulus
d
w
43
m
Adjustable parameter
α
0.4
Adjustable parameter
β
0.3
Adjustable parameter
γ
0.3
Power consumption on idle listening
P
m
0.05
J/s
Power consumption on light sleeping
P
l
0.002
J/s
Power consumption on deep sleeping
P
d
0.001
J/s
Power consumption on state switching between idle listening and light sleeping mode
P
l
′
0.0002
J/s
Power consumption on state switching between idle listening and deep sleeping mode
P
d
′
0.0004
J/s
Switching time between idle listening and light sleeping mode
t
l
0.2
s
Switching time between idle listening and deep sleeping mode
t
d
0.4
s
Rate of sampling
u
100
Bit/s
Rate of data sending
v
t
10 k
Bit/s
Rate of data receiving
v
r
10 k
Bit/s


### 5.1. Discussion about the Value ofq

Similar to [29], the nonuniform deployment model is adopted in SNAA, which could reduce the burden of nodes near the center and achieve energy balance. As mentioned in Section 3.2, the value of q is not only important for the probability that nodes find their parent in the candidate region, but also related to the redundancy of network. Thus, it is discussed as follows.According to formula (16) as well as the parent selection strategy in SNAA, for a node Si in the Nth annulus, the expected value of the number of its candidate parents in the candidate region is(30)nSi=SiFminNumN-1SN-1=0.5πdw2NumNδqπdw22N-3=NumNδq22N-3.For convenience, the values ofN and δ are set to be 4 and 0.8 in (30). The relationship between n(Si) and q is shown in Figure 11 when the value of NumN is 8, 10, and 12, respectively. It is easy to know that the number of the candidate nodes in the candidate region increases with the raise of q, no matter what the value of NumN is. Therefore, the high value of q could increase the probability of finding the parent node which effectively mitigates the energy hole problem caused by network disconnection.Figure 11
Number of nodes in the candidate region with the increase ofq.On the other hand, the value ofNumN is also important for the probability of selecting the optimal parent node. In Figure 11, when NumN=8, the value of q should be higher than 1.6 to ensure that there is at least one candidate node in the candidate region, while when NumN=12, to satisfy the same requirement, q only needs to be not less than 1.1.Figure12 shows the residual energy of nodes at the end of the network lifetime. It is obvious that the residual energy of each node has a low value in Figure 12 (not higher than 2.2 J), which has a good performance on energy balance. Moreover, the residual energy of nodes in the same annulus is nearly the same which could effectively mitigate the energy hole problem.Figure 12
Residual energy of nodes.The deployments of nodes in this experiment are shown in Figures13–15 and the numbers of nodes in each annulus are shown in Table 2. According to formula (24), it is known that the number of nodes in the Nth annulus should be not less than 4N-6. Thus, in this simulation, this value is 10. Therefore, when NumN=8, nodes may have no candidate parents in the candidate region, especially for the one in the outer annulus. So they may fail to communicate with their neighbors synchronously which could easily cause unbalanced energy consumption. Moreover, when NumN=12 and q=1.1, the numbers of nodes in each annulus are approximately equal. So energy consumption on nodes near the center is larger than others which could not reach the best result as well.Table 2
Number of nodes in each annulus with differentq.
q
Num1
Num2
Num3
Num4
n
1.1
13
12
11
12
48
1.3
18
14
10
10
52
1.6
26
16
10
8
60Figure 13
Network deployment whenq=1.1 and NumN=12.Figure 14
Network deployment whenq=1.3 and NumN=10.Figure 15
Network deployment whenq=1.6 and NumN=8.Figures16 and 17 describe the total residual energy about all nodes as well as the mean value of residual energy of each node in SNAA, respectively. It is known that, at the end of the network lifetime, total residual energy is no more than 1.8%  nE0 (when q=1.3 and NumN=10, the value is only about 1%  nE0). Thus, the energy hole problem has been mitigated in SNAA.Figure 16
Total residual energy about all nodes.Figure 17
Mean value of residual energy of each node.Variance of the residual energy, the network lifetime, and the data received by all nodes during their lifetime are shown in Table3. It is known that there are little differences about the network lifetime under different deployment model. However, when q=1.3 and NumN=10, the efficiency on data collection and the performance of energy balance are better than others, because, in this case, the loads on nodes near the center are relatively low, while when NumN=8 and q=1.6, the number of nodes in the first annulus is 26, which easily leads to redundant deployment problem.Table 3
Variance of residual energy, network lifetime, and data received by all nodes during their lifetime.
N
u
m
N
q
Variance of the residual energy
Network lifetime
Data received by all nodes
12
1.1
0.5122 J2
1920 s
7434 Kbits
10
1.3
0.2680 J2
1943 s
8144 Kbits
8
1.6
0.3539 J2
1930 s
9334 Kbits


### 5.2. Analysis on the Value ofχ

As mentioned above, all the active nodes check their residual energy at the end of eachT in SNAA. When Er/Er′<χ, the node should go into sleeping mode. Thus, the value of χ is related to the efficiency of data gathering as well as the network lifetime and should be discussed as follows. The values of the parameters in this section are shown in Table 4.Table 4
Parameter values in Section5.2.
Parameter
Symbol
Value
Number of annuluses
N
4
Number of nodes in theNth annulus
NumN
10
Ratio of two adjacent annuluses
q
1.3
Adjustable parameter
χ
50%
Adjustable parameter
δ
0.8The total residual energy about all nodes and their variances with different values ofχ are shown in Figures 18 and 19, respectively. It is known that, at the end of the network lifetime, the two kinds of values are relatively stable no matter what the value of χ is. This is because a relatively reasonable deployment strategy is used in SNAA and the optimal parent selection scheme is also proposed by considering the residual energy as well as the communication distance of nodes. From Figures 18 and 19, it is also known that the best value of χ is 50%. When χ is small, it is not easy for nodes to go into sleeping mode; thus, the “hotspot” may appear. On the contrary, nodes may frequently enter into sleeping mode when χ is large. This could save more energy, but the efficiency is relatively low. Therefore, the value of χ should be neither too large nor too small.Figure 18
Total residual energy about all nodes with different values ofχ.Figure 19
Variances of residual energy with different values ofχ.Figure20 shows the data receiving rate with different χ. At the end of the network lifetime, there are still some data being transmitted and not received by sink. Thus, few pieces of data could be discarded in SNAA. It is known from Figure 20 that when χ=50%, the efficiency of data collection is relatively high.Figure 20
Data receiving rate with different values ofχ.


### 5.3. Comparison with Other Energy Hole Mitigating Methods

To further analyze the performance of SNAA on energy balance as well as the execution efficiency, we compare it with the other two energy hole mitigating methods in [4] and [29], respectively. Values of parameters used in these experiments are shown in Algorithm 1 and Table 3, while χ=50%.The residual energy of the whole network in the three methods is shown in Figure21. The value in SNAA decreases slowly and tends to be stable. This is because each active node in SNAA collects, sends, and receives data synchronously in T, which ensures that the energy consumption values about them are nearly the same. Although the algorithms in [4, 29] could also mitigate the energy hole problem, their residual energy decreases a little faster than SNAA. Furthermore, it is known that the network lifetime in [4, 29] is 1600 and 1200 rounds, respectively, which is also shorter than SNAA. Thus, SNAA could effectively prolong the network lifetime by reducing the energy consumption on communication as well as idle listening.Figure 21
Total residual energy in different algorithms.Figure22 shows the variation of the residual energy about all nodes in the three algorithms. Due to the nonuniform deployment strategy which reduces the energy consumption of nodes near the center, both of the algorithms show a good performance on energy balance. With the help of the optimal width of the annulus, nodes are deployed proportionally in [4], but the “unbalanced load problem” for nodes is not considered. While the value of the proportion in [29] is a little big, more nodes could be deployed near the center. In addition, the parent selection strategies in [4, 29] are only based on the residual energy of the candidate nodes and the communication distance between the nodes in adjacent annuluses is not considered. Therefore, the effect of SNAA on energy balance is better than the two others.Figure 22
Variation of the residual energy in different algorithms.Network lifetime in the three algorithms with different network sizes is shown in Figure23. It is known that the values are relatively stable in [4, 29]. With the help of the sleeping scheduling strategy, there may be more and more nodes that could go into sleeping mode in SNAA. Therefore, the network lifetime increases with the increase of the number of annuluses. However, if N>9, the amount of data transmitted by the nodes near the center will also increase. In this case, nodes in SNAA will die quickly.Figure 23
Network lifetime in different algorithms.


## 5.1. Discussion about the Value ofq

Similar to [29], the nonuniform deployment model is adopted in SNAA, which could reduce the burden of nodes near the center and achieve energy balance. As mentioned in Section 3.2, the value of q is not only important for the probability that nodes find their parent in the candidate region, but also related to the redundancy of network. Thus, it is discussed as follows.According to formula (16) as well as the parent selection strategy in SNAA, for a node Si in the Nth annulus, the expected value of the number of its candidate parents in the candidate region is(30)nSi=SiFminNumN-1SN-1=0.5πdw2NumNδqπdw22N-3=NumNδq22N-3.For convenience, the values ofN and δ are set to be 4 and 0.8 in (30). The relationship between n(Si) and q is shown in Figure 11 when the value of NumN is 8, 10, and 12, respectively. It is easy to know that the number of the candidate nodes in the candidate region increases with the raise of q, no matter what the value of NumN is. Therefore, the high value of q could increase the probability of finding the parent node which effectively mitigates the energy hole problem caused by network disconnection.Figure 11
Number of nodes in the candidate region with the increase ofq.On the other hand, the value ofNumN is also important for the probability of selecting the optimal parent node. In Figure 11, when NumN=8, the value of q should be higher than 1.6 to ensure that there is at least one candidate node in the candidate region, while when NumN=12, to satisfy the same requirement, q only needs to be not less than 1.1.Figure12 shows the residual energy of nodes at the end of the network lifetime. It is obvious that the residual energy of each node has a low value in Figure 12 (not higher than 2.2 J), which has a good performance on energy balance. Moreover, the residual energy of nodes in the same annulus is nearly the same which could effectively mitigate the energy hole problem.Figure 12
Residual energy of nodes.The deployments of nodes in this experiment are shown in Figures13–15 and the numbers of nodes in each annulus are shown in Table 2. According to formula (24), it is known that the number of nodes in the Nth annulus should be not less than 4N-6. Thus, in this simulation, this value is 10. Therefore, when NumN=8, nodes may have no candidate parents in the candidate region, especially for the one in the outer annulus. So they may fail to communicate with their neighbors synchronously which could easily cause unbalanced energy consumption. Moreover, when NumN=12 and q=1.1, the numbers of nodes in each annulus are approximately equal. So energy consumption on nodes near the center is larger than others which could not reach the best result as well.Table 2
Number of nodes in each annulus with differentq.
q
Num1
Num2
Num3
Num4
n
1.1
13
12
11
12
48
1.3
18
14
10
10
52
1.6
26
16
10
8
60Figure 13
Network deployment whenq=1.1 and NumN=12.Figure 14
Network deployment whenq=1.3 and NumN=10.Figure 15
Network deployment whenq=1.6 and NumN=8.Figures16 and 17 describe the total residual energy about all nodes as well as the mean value of residual energy of each node in SNAA, respectively. It is known that, at the end of the network lifetime, total residual energy is no more than 1.8%  nE0 (when q=1.3 and NumN=10, the value is only about 1%  nE0). Thus, the energy hole problem has been mitigated in SNAA.Figure 16
Total residual energy about all nodes.Figure 17
Mean value of residual energy of each node.Variance of the residual energy, the network lifetime, and the data received by all nodes during their lifetime are shown in Table3. It is known that there are little differences about the network lifetime under different deployment model. However, when q=1.3 and NumN=10, the efficiency on data collection and the performance of energy balance are better than others, because, in this case, the loads on nodes near the center are relatively low, while when NumN=8 and q=1.6, the number of nodes in the first annulus is 26, which easily leads to redundant deployment problem.Table 3
Variance of residual energy, network lifetime, and data received by all nodes during their lifetime.
N
u
m
N
q
Variance of the residual energy
Network lifetime
Data received by all nodes
12
1.1
0.5122 J2
1920 s
7434 Kbits
10
1.3
0.2680 J2
1943 s
8144 Kbits
8
1.6
0.3539 J2
1930 s
9334 Kbits


## 5.2. Analysis on the Value ofχ

As mentioned above, all the active nodes check their residual energy at the end of eachT in SNAA. When Er/Er′<χ, the node should go into sleeping mode. Thus, the value of χ is related to the efficiency of data gathering as well as the network lifetime and should be discussed as follows. The values of the parameters in this section are shown in Table 4.Table 4
Parameter values in Section5.2.
Parameter
Symbol
Value
Number of annuluses
N
4
Number of nodes in theNth annulus
NumN
10
Ratio of two adjacent annuluses
q
1.3
Adjustable parameter
χ
50%
Adjustable parameter
δ
0.8The total residual energy about all nodes and their variances with different values ofχ are shown in Figures 18 and 19, respectively. It is known that, at the end of the network lifetime, the two kinds of values are relatively stable no matter what the value of χ is. This is because a relatively reasonable deployment strategy is used in SNAA and the optimal parent selection scheme is also proposed by considering the residual energy as well as the communication distance of nodes. From Figures 18 and 19, it is also known that the best value of χ is 50%. When χ is small, it is not easy for nodes to go into sleeping mode; thus, the “hotspot” may appear. On the contrary, nodes may frequently enter into sleeping mode when χ is large. This could save more energy, but the efficiency is relatively low. Therefore, the value of χ should be neither too large nor too small.Figure 18
Total residual energy about all nodes with different values ofχ.Figure 19
Variances of residual energy with different values ofχ.Figure20 shows the data receiving rate with different χ. At the end of the network lifetime, there are still some data being transmitted and not received by sink. Thus, few pieces of data could be discarded in SNAA. It is known from Figure 20 that when χ=50%, the efficiency of data collection is relatively high.Figure 20
Data receiving rate with different values ofχ.


## 5.3. Comparison with Other Energy Hole Mitigating Methods

To further analyze the performance of SNAA on energy balance as well as the execution efficiency, we compare it with the other two energy hole mitigating methods in [4] and [29], respectively. Values of parameters used in these experiments are shown in Algorithm 1 and Table 3, while χ=50%.The residual energy of the whole network in the three methods is shown in Figure21. The value in SNAA decreases slowly and tends to be stable. This is because each active node in SNAA collects, sends, and receives data synchronously in T, which ensures that the energy consumption values about them are nearly the same. Although the algorithms in [4, 29] could also mitigate the energy hole problem, their residual energy decreases a little faster than SNAA. Furthermore, it is known that the network lifetime in [4, 29] is 1600 and 1200 rounds, respectively, which is also shorter than SNAA. Thus, SNAA could effectively prolong the network lifetime by reducing the energy consumption on communication as well as idle listening.Figure 21
Total residual energy in different algorithms.Figure22 shows the variation of the residual energy about all nodes in the three algorithms. Due to the nonuniform deployment strategy which reduces the energy consumption of nodes near the center, both of the algorithms show a good performance on energy balance. With the help of the optimal width of the annulus, nodes are deployed proportionally in [4], but the “unbalanced load problem” for nodes is not considered. While the value of the proportion in [29] is a little big, more nodes could be deployed near the center. In addition, the parent selection strategies in [4, 29] are only based on the residual energy of the candidate nodes and the communication distance between the nodes in adjacent annuluses is not considered. Therefore, the effect of SNAA on energy balance is better than the two others.Figure 22
Variation of the residual energy in different algorithms.Network lifetime in the three algorithms with different network sizes is shown in Figure23. It is known that the values are relatively stable in [4, 29]. With the help of the sleeping scheduling strategy, there may be more and more nodes that could go into sleeping mode in SNAA. Therefore, the network lifetime increases with the increase of the number of annuluses. However, if N>9, the amount of data transmitted by the nodes near the center will also increase. In this case, nodes in SNAA will die quickly.Figure 23
Network lifetime in different algorithms.


## 6. Conclusion

To achieve energy balance in a circular sensor network, a type of energy hole avoiding method based on synchronization of nodes in adjacent annuluses is proposed in this paper. Nodes are deployed nonuniformly in each annulus, which effectively reduces the energy consumption on nodes near the center. Furthermore, the optimal parent node selection method and the sleep scheduling strategy are also proposed in SNAA to further mitigate the energy hole problem. However, the problem on data transmission delay is also important in the circular network and should be studied in our future work to further improve the performance of SNAA.



---

*Source: 5828956-2016-03-28.xml*