# A Reliability-Oriented Local-Area Model for Large-Scale Wireless Sensor Networks

Authors: Haixia Peng; Hai Zhao; Yuanguo Bi; Shuaizong Si; Wei Cai
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Large-scale wireless sensor networks (WSNs) have demonstrated some complex features which are similar to those of other types of complex networks, such as social networks. Based on these complex features, evolution process and characteristic of WSNs, we represent a WSN topologically by building a suitable model, which is named as the reliability-oriented local-area model (ROLM) and aimed at improving the performance of WSNs. For analyzing the performance of the ROLM, we define the reliability as the probability of that the relative error between the measurement and the true value is equal to or less thanε  (
ε
≥
0
) and proposed a parameter η to measure the reliability of the network. Based on them, we use η to analyze the influence of network structure on the reliability, and compared the reliabilities of the ROLM and the existing WSNs. Experiment results prove that the large-scale WSN follows a power-law distribution, and it has scale-free characteristic and small world characteristic. And it also shows that, comparing with existing model, ROLM not only balances energy consumption by limiting the connectivity of each node to prolong the lifetime of the network, but also improves the reliability substantially. And the ROLM can be used to express the topology of reliability-oriented WSNs and analyze the structure preferably.


---

## Body

## 1. Introduction

Complex networks are currently being studied in many scientific fields [1] and many systems actually can be described through complex networks such as biological networks [2], metabolic networks [3], social networks [4], software network [5], scientific collaboration networks [6], and World Wide Web [7, 8]. Wireless sensor networks (WSNs), as a particular type of complex networks, are different from other types of complex networks. A large-scale WSN consists of a large number of distributed sensor nodes, and therefore a large-scale WSN has some complex features of complex networks [9]. Due to short communication range and energy constraints, these sensor nodes autonomously establish connections through wireless communications with the other nodes that are within their local-area. Here the concept of local-area can be seen as a domain surrounding these nodes where their signals can be reached. In fact, there is also local-area in other networks, for example, a community structure in social networks, a regional cooperative group in economic networks, and a domain in the internet, all of which are local-areas.In order to model a WSN, most researches consider that the WSN consists of the same types of nodes and links. Reference [10] shows that it is possible to model a WSN as a small world network by using multiple cluster nodes that can emulate the long edge required in small world networks. In [11], a novel evolving network model is based on random walk to study the fault tolerance of the WSN due to node failure and discuss the spreading dynamic behavior of viruses in the evolution model. Considering the diversities of nodes and links in a real WSN, [9] proposes a local-world heterogeneous model for the WSN. In [9], nodes are divided into two classes: sensor nodes (SNs) and cluster-head nodes (CHs), and there are two kinds of links: the bidirectional edge between CHs (CH↔CH) and the directional link pointing to CHs from SNs (SN→CH). The model in [9] is different from the aforementioned models with homogeneous nodes and links, and it balances energy consumption by limiting the connectivity of CHs to prolong the lifetime of the network. However, recent advancements in wireless communications and sensor technologies have enabled most SNs to relay data packets [12]; that is, there are always SN↔SN in many practical applications. Reference [9] only considers two kinds of links and neglects the links among SNs, which makes the model in [9] be not suitable for most current practical applications.On the other hand, in practical WSN applications, SNs are usually deployed in some inaccessible and dangerous environments to gather information from the physical world to a sink node (base station); for example, WSNs can be used to monitor environmental changes (such as weather, gas in coal mine) [13, 14], monitor habitats [15, 16], track objects [17], manage disasters [18], and so on. Most recent researches about WSNs try to improve energy efficiency and prolong the lifetime of the network. Several international research projects dedicated to energy-efficient (EE) wireless communications have been carried out. In [19], a link-adaptive transmission scheme for MIMO-OFDM systems is proposed, which maximizes EE in terms of bits-per-Joule using dynamic power allocation based on the channel state as well as the circuit power consumption. Based on the complex network theory, a new topological evolving model is proposed in. In the evolution of the topology of sensor networks, the energy-aware mechanism is taken into account, and the phenomenon of change of the link and node in the network is discussed. Although they are energy-efficient and have long lifetime, they are not suitable for some applications with the requirement of high reliability (this is critically important in some study of the WSN [20], and the concept of reliability will be given in the next section). Reference [21] shows that, in WSNs, due to environment noise, reliable data communications cannot be definitely achieved. Even under ideal conditions, the packet loss rate of a WSN may be above 1% or close to 1% due to packet collisions. When the communication environment becomes hostile, the packet loss rate will definitely go up, and a successful data transmission over links in the WSN can be guaranteed with a certain probability (less than 100%). As most applications of WSNs need to aggregate sensed data from environment [20], and if we want to aggregate the sensed data in the network, just a part of sensed data from SNs will be sent to the sink node, the aggregation result provided by the WSN cannot be ensured to be accurate, and there is a need to study this issue for WSN’s some aggregation operators. As we define the reliability to describe this issue in our research, we call this issue as the reliability of WSN. Even though some researches such as [9] can prolong the lifetime of WSNs through balancing energy consumption, the reliability of the WSN should also be taken into account for reliable data communications.For the above reasons, a reliability-oriented network model which is consistent with the actual network is very important to the WSN application development. In this paper, we propose a reliability-oriented local-area model for the WSN with the help of growth and preferential attachment mechanism. The influence of the local-area scaleC, the scale of WSNs, the strategy of evolution on the reliability of WSNs, and topological properties are investigated. Firstly, to measure the reliability of the WSN, we present the concept of reliability and verify its mathematical rationality and find that the reliability η of a large-scale WSN can be represented as a function of the maximum value ω of cluster layer of SNs. Secondly, we show that this model has intrinsic characteristics, the assortative connectivity correlation, and characteristic of power law. The energy efficiency of this model is better than that of [9], and the lifetime is identical and it has higher reliability compared with the model in [9]. Moreover, from the perspective of the reliability of the WSN, we reveal that the reliability of the WSN evolving from ROLM is much better than that of [9], and when the network scale is larger than 1000, the reliability of the WSN evolving from [9] is far less than that of the ROLM.


## 2. Model of WSNs

There are two kinds of nodes (SNs and CHs, which will be identified by IEEE address [22]) in the WSN: the SNs will connect with a CH or other SNs, and the CHs can connect with the sink node or other CHs. These two kinds of nodes perform different functions in the WSN evolving from ROLM, such that SN is responsible for sensing information from geographical environment and sending its sensed data to a CH which it belongs to, while a CH collects sensed data from its cluster members. After processing the whole data it will retransmit the aggregation result to the next hop CH. Considering the complex futures of WSNs, ROLM is designed based on the existing complex system modeling method. Take BA model, for example, [23]. There is one new-incoming node entering a preexisting network at every step and choosing one or some nodes from the preexisting network to connect with a certain probability. After a node connects to the network, there will be another new-incoming node entering the network in the next step until the number of nodes in this network reaches the preset network scale.As a special kind of complex networks, WSNs have some specific characteristics. Therefore, we should consider some factors such as the node transmission range, the hop-constraints between nodes, the reliability of network, and transmission delay. In WSNs, because of the constraint of node transmission range, each node in the network can only communicate with those nodes located within its coverage, which is named as local-area connections. On the other hand, when the monitoring area has the similar condition, every wireless link (the link between two nodes which has one hop between them) in the network has the same packet loss probability, which means that the sensed data will be sent successfully over one link with a probabilityq (q
≤
1) [24]. And apparently, if the sensed data has to be delivered to a node two hops away, then it will be over two links and the successful transmission probability of this data is q
2. As the probability q is equal to or less than 1, the more hops the sensed data needs to be delivered, the lower the probability that the sensed data will be sent successfully to the sink node. Therefore, just a part of sensed data will be sent to the sink node when the WSN performing an aggregation operator and the reliability of the WSN for this aggregation operator will decrease consequently. ROLM tries to reduce the number of links between two connected nodes to improve the reliability. Based on the local-area and fitness models in complex networks theory, this paper studies the evolution model while considering the constraints of transmission range and the reliability of the WSN in a novel approach.


### 2.1. Problem Definition

To facilitate researching on ROLM and the reliability of the WSN evolving from ROLM in this paper, we will briefly introduce some related definitions as follows in this part. It includes sink layer, cluster layer, round,ε-estimate, reliability, η, unbiased estimate, and round.Definition 1 (sink layer).
For nodei (CH or SN), if its father node is the sink node, then we define that its sink layer is 1 and express it as ω
i
=
1; if its father node j’s ω
j
=
1, then its ω
i
=
2, and so on.Definition 2 (cluster layer).
For aSN
i, if its father node is a CH, then we define that its cluster layer is 1 and express it as ω
s
i
=
1; if its father node j’s ω
s
j
=
1, then its ω
s
i
=
2, and so on.The concepts ofω
i and ω
s
i show that CH
i has only value of ω
i; and SN
j has both ω
j and ω
s
j, and the values of ω
j and ω
s
j for SN
j are different.Definition 3 (degree).
The total number of links pointing to nodei from other nodes is called the degree of node i, expressed in k
i. If node i can connect with the other k
max
⁡
i nodes, then define its saturated degree as k
max
⁡
i.There are many types of aggregation result (Sum, Average, Max, and so on) which we can get from the WSNs [25]. In order to specifically study the reliability of the WSN evolving from ROLM, we take the SUM aggregation operator as an example and propose the concept of reliability and η parameter to measure the reliability of the WSN. For the other aggregation operator, their processing methods are the same as that of SUM aggregation operator, such that we can get the Average result from the process of calculating the Sum result (the sum value in every cluster divided by the number of members of this cluster, and then the CH will transfer their quotient values to the sink node).At timet, if the WSN can only aggregate a part of sensed data from its nodes, it will provide an approximated SUM, expressed in Sum
(
S
t
)
′. If it aggregates all sensed data in the WSN, it will get an accurate SUM, called Sum
(
S
t
).Definition 4 (ε-estimate).
Sum
(
S
t
)
′ is called an ε-estimate of Sum
(
S
t
) if |
(
Sum
(
S
t
)
′
-
Sum
(
S
t
)
)
/
Sum
(
S
t
)
|
≤
ε for any ε (ε
≥
0).Definition 5 (reliability).
For a given network andε (ε
≥
0), reliability is the probability of that Sum
(
S
t
)
′ is the ε-estimate of Sum
(
S
t
) [20].Definition 6 (η).
For a given network andε (ε
≥
0), η (0
≤
η
≤
1) is the lower bound of probability of that Sum
(
S
t
)
′ is the ε-estimate of Sum
(
S
t
); that is, η
≤
P
(
|
(
Sum
(
S
t
)
′
-
Sum
(
S
t
)
)
/
Sum
(
S
t
)
|
≤
ε
).Definition 7 (unbiased estimate).
Sum
(
S
t
)
′ is an unbiased estimate of Sum
(
S
t
) if the mathematical expectation of Sum
(
S
t
)
′ is equal to Sum
(
S
t
); that is, E
(
Sum
(
S
t
)
′
)
=
Sum
(
S
t
); otherwise Sum
(
S
t
)
′ is a biased estimator of Sum
(
S
t
).Definition 8 (round).
The amount of time from the sink node initiates a data collection command to all sensed data from SNs being sent to the sink node, no matter how long it will last. This amount of time is called one round.


### 2.2. Reliability-Oriented Local-Area Model

In this section, we model a WSN as a network with growth and preferential attachment and propose an evolution model ROLM with high reliability. Different from [9], the WSN evolving from ROLM includes three kinds of links. They are the bidirectional link between CHs (CH↔CH), the directional link from SN to CH (SN→CH), and the bidirectional link between SNs (SN↔SN). For CH
i, let k
c
i be the current degree that is the total number of links pointing to CH
i from other nodes, and let E
c
i be its initial energy value. And for a SN
i, provide that k
s
i is the degree that is the total number of links pointing to SN
i from other SNs and E
s
i represents the initial energy value of SN
i. Define that E
c
i is a random variable following the uniform distribution ρ
(
E
c
) in the interval [
E
min
⁡
c
,
E
max
⁡
c
] and E
s
i is a random variable following the uniform distribution ρ
(
E
s
) in the interval [
E
min
⁡
s
,
E
max
⁡
s
]. Set E
c
i as much larger than E
s
i. Here, E
max
⁡
c
≥
E
min
⁡
c
≥
E
max
⁡
s
≥
E
min
⁡
s, E
max
⁡
c is the maximum initial energy of CHs, and a CH with E
maxc could connect with less than k
max
⁡
c nodes. Similarly, E
max
⁡
s is the maximum initial energy of SNs, and the SN with E
maxs could connect with less than k
max
⁡
s SNs. Let k
max
⁡
c
i and k
max
⁡
s
i be the saturated degree of CH
i and SN
i respectively; then we define(1)
k
max
⁡
c
i
=
k
max
⁡
c
E
c
i
E
max
⁡
c
,
k
max
⁡
s
i
=
k
max
⁡
s
E
s
i
E
max
⁡
s
.The basic settings for ROLM can be described as  shown in Algorithm1.Algorithm 1
//defining the variables
C
H
i:
Var k
c
i, E
c
i
S
N
i:
Var k
s
i, E
s
i
Begain
/////////////////////////////////////////////////////
//the types of node in ROLM
Fori
=
1 to NumberOfNetworks do
{
probability P:
nodeKind =
= CH;
probability 1
-
P:
nodeKind =
= SN;
}
//initializing node energy
Fori
=
1 to NumberOfNetworks do
{
If nodeKind=
= CH
E
c
i
=
ρ
(
E
c
); //the initial energy value of C
H
i
Else if nodeKind=
= SN
E
s
i
=
ρ
(
E
s
);  //the initial energy value of S
N
i, and E
max
⁡
c
≥
E
min
⁡
c
≥
E
max
⁡
s
≥
E
min
⁡
s
}
//calculating the saturated degree ofC
H
i and S
N
i
Fori
=
1 to NumberOfNetworks do
{
k
max
⁡
c
i
=
k
max
⁡
c
E
c
i
E
max
⁡
c; //the saturated degree of C
H
i, and set the value of k
max
⁡
c to be 20
k
max
⁡
s
i
=
k
max
⁡
s
E
s
i
E
max
⁡
s; //the saturated degree of S
N
i, and set the value of k
max
⁡
s to be 7
}The growth in the WSN evolving from ROLM is starting with an existing network with a small number ofc
0 nodes (all of these c
0 nodes are connected with each other. As SNs connect to the sink node by CHs, there must be at least one CH among these c
0 nodes). Referring to the BA modeling method in complex networks, ROLM can be described as follows.(
a
)
At every step, a new-incoming node (CH or SN) connects to one node in an existing network. If the new-incoming node is a CH with energy valueE
c
i, it may connect to the other CHs within its local-area, while if the new-incoming node is a SN with energy value E
s
i, it may connect to a CH or a SN within its local-area. For a new-incoming CH, it enters the preexisting network with probability p (the probability p is the proportion of CHs in the WSN evolving from ROLM), as new-incoming nodes include CHs and SNs; thus the proportion of SNs in the WSN evolving from ROLM is (
1
-
p
), and the probability for a new-incoming SN entering the preexisting network is (
1
-
p
).
(
b
)
Preferential attachment: the new-incoming CH connects to a selected CH in the preexisting network, and the new-incoming SN connects to a selected CH or a SN from the preexisting network. In this case, as the node in WSNs has the constraints of energy and connectivity, it only communicates with one CH or SN in the local-area to avoid data redundancy. Firstly, we markC nodes randomly from the preexisting network as the local-area Φ. As the scale of local-area Φ is based on the new-incoming node’s communication range, and the directly connected nodes of each node are chosen from these C nodes, we set C
≥
max
⁡
{
k
max
⁡
s
,
k
max
⁡
c
}. Considering that nodes have constraints of energy and connectivity, and ROLM is trying to improve the reliability of the WSN for some aggregation operators, in the WSN evolving from ROLM, the new-incoming nodes (CHs or SNs) will connect to CH
i in the local-area Φ according to the probability ∏
c
i, and SN
i in the local-area Φ will be connected by new-incoming SNs according to the probability ∏
s
i:(2)
∏
c
i
=
E
r
c
i
k
c
i
/
ω
i
∑
j
∈
Φ
E
r
c
j
k
c
j
/
ω
j
(3)
∏
s
i
=
E
r
s
i
k
s
i
/
ω
i
∑
j
∈
Φ
E
r
s
j
k
s
j
/
ω
j
,
whereE
r
c
i and E
r
s
i are the residual energy of CH
i and SN
i.
Considering the fact that every link connected to nodei will consume some energy of node i, we simply define(4)
E
r
c
i
=
E
c
i
-
b
k
c
i
,
(5)
E
r
s
i
=
E
s
i
-
b
k
s
i
,
whereb is a constant and can be regarded as the energy consumed by every link. Formulas (4) and (5) mean that the closer the degree of node i is to k
max
⁡
c
i or k
max
⁡
s
i, the less the residual energy of the node i will be left. Replacing E
r
c
i and E
r
s
i with (4) and (5) in formulas (2) and (3), respectively, we can get(6)
∏
c
i
=
(
E
c
i
-
b
k
c
i
)
/
ω
i
∑
j
∈
Φ
(
E
c
j
-
b
k
c
j
)
/
ω
j
,
∏
s
i
=
(
E
s
i
-
b
k
s
i
)
/
ω
i
∑
j
∈
Φ
(
E
s
j
-
b
k
s
j
)
/
ω
j
.
(
c
)
After step (b), when a new-incoming SN enters into the preexisting network, and if the degree of an existingSN
i is k
s
i
<
k
max
⁡
s
i, return to step (b); otherwise remove SN
i from the local-area Φ; that is to say, a new node cannot connect to this SN
i even though SN
i is within the local-area Φ. When a new-incoming node (CH or SN) enters into the pre-existing network, if the degree of CH
i is k
c
i
<
(
k
max
⁡
c
i
-
1
) (it could avoid all these k
max
⁡
c
i nodes connected to one CH
i are SNs, and the new-incoming CH cannot joint into the pre-existing network as all CHs within the local-area Φ have reached their saturated degrees), and the new-incoming node is a SN, then return to step (b), otherwise remove CH
i from the local-area Φ; if the degree of CH
i is k
c
i
<
k
max
⁡
c
i, and the new-incoming node is a CH, then return to step (b), otherwise remove CH
i from the local-area Φ.The description of ROLM with pseudocode  is shown as in Pseudocode1.Pseudocode 1
//starting with an existing network with a small number ofc
0 nodes and at least one CH node among them
//using the Function_ROLM_Model to construct the WSN
Function_ROLM_Model
Begain
Form
=
1 to NumberOfNetworks do
{
//Firstly, we markC nodes randomly from the pre-existing network as the local-area Φ
local-areaΦ: C nodes, C
≥
max
⁡
{
k
max
⁡
s
,
k
max
⁡
c
}
If nodeKind=
= SN
{
For i
=
1 to C do
{
If k
s
i
≤
k
max
⁡
s
i
{
∏
s
i
=
E
r
s
i
k
s
i
/
ω
i
∑
j
∈
Φ
E
r
s
j
k
s
j
/
ω
j; //E
r
s
i is the residual energy of S
N
i, ω
i and ω
j are
the sink layer values of node i and node j
/
}
/
}
node(i) = max
⁡
(
∏
s
i
); //select the node with max probability ∏
s
i from the local-area Φ
CONNECT(node(m), node(i)); //connect node(m) & node(i), link(m
,
i)
E
r
s
i
=
E
s
i
-
b
k
s
i; //b is regarded as the energy consumed by every link
k
s
i
+
=
1;
/
}
Else if nodeKind=
= CH
{
For i
=
1 to C do
{
Ifk
c
i
<
(
k
max
⁡
c
i
-
1
) && nodeKind =
= CH
{
∏
c
i
=
E
r
c
i
k
c
i
/
ω
i
∑
j
∈
Φ
E
r
c
j
k
c
j
/
ω
j; //E
r
c
i is the residual energy of C
H
i. ω
i and ω
j are
the sink layer values of nodei and node j
/
}
/
}
Node(i) = max
⁡
(
∏
c
i
); //select the node with max probability ∏
s
i from the local-area Φ
CONNECT(node(m), node(i)); //connect node(m) & node(i
), link(m
,
i)
E
r
c
i
=
E
c
i
-
b
k
c
i; //b is regarded as the energy consumed by every link
k
c
i
+
=
1;
/
}
/
}
End_ROLMFor a WSN with a certain number of nodes, through the above three steps, the nodes in the WSN can be connected with each other. When the number of nodes is 5000,k
max
⁡
s
=
7, k
max
⁡
c
=
20, the topology graph is shown in Figure 1(a), and Figure 1(b) is an example for detailed topology of one cluster in Figure 1(a). The three steps of ROLM show that the probability of a new-incoming node connecting to a preexisting CH
i or SN
i not only depends on its current state: k
c
i  (or k
s
i) and ω
c
i  (or ω
s
i) but also has the constraint of k
c
i
<
k
max
⁡
c
i
≤
k
max
⁡
c (or k
s
i
<
k
max
⁡
s
i
≤
k
max
⁡
s), and k
c
i (k
s
i) depends on the node i’s initial energy. ROLM has considered the diversities of nodes and links and balanced the energy consumption globally by limiting the links to a CH and the links to a father SN. Furthermore, it also improves the reliability of WSNs for an aggregation operator (the smaller the ω
s
i is, the higher the reliability of WSNs will be, and it will be proved in the next section for SUM aggregation operator) without shortening the lifetime of the network. As high-reliability and energy efficiency are both critically important for most WSNs applications [26, 27], the WSN evolving from ROLM can perform more efficiently under such environment.Figure 1
The topology graph and subgraph of topology of the WSN, where nodes’ sizes represent their current degree, the nodes’ color reflects their community structure, nodes with the same color means that they have the same modularity, and the communication among them will be more frequent.
(a)
Topology graph
(b)
Subgraph of topology


## 2.1. Problem Definition

To facilitate researching on ROLM and the reliability of the WSN evolving from ROLM in this paper, we will briefly introduce some related definitions as follows in this part. It includes sink layer, cluster layer, round,ε-estimate, reliability, η, unbiased estimate, and round.Definition 1 (sink layer).
For nodei (CH or SN), if its father node is the sink node, then we define that its sink layer is 1 and express it as ω
i
=
1; if its father node j’s ω
j
=
1, then its ω
i
=
2, and so on.Definition 2 (cluster layer).
For aSN
i, if its father node is a CH, then we define that its cluster layer is 1 and express it as ω
s
i
=
1; if its father node j’s ω
s
j
=
1, then its ω
s
i
=
2, and so on.The concepts ofω
i and ω
s
i show that CH
i has only value of ω
i; and SN
j has both ω
j and ω
s
j, and the values of ω
j and ω
s
j for SN
j are different.Definition 3 (degree).
The total number of links pointing to nodei from other nodes is called the degree of node i, expressed in k
i. If node i can connect with the other k
max
⁡
i nodes, then define its saturated degree as k
max
⁡
i.There are many types of aggregation result (Sum, Average, Max, and so on) which we can get from the WSNs [25]. In order to specifically study the reliability of the WSN evolving from ROLM, we take the SUM aggregation operator as an example and propose the concept of reliability and η parameter to measure the reliability of the WSN. For the other aggregation operator, their processing methods are the same as that of SUM aggregation operator, such that we can get the Average result from the process of calculating the Sum result (the sum value in every cluster divided by the number of members of this cluster, and then the CH will transfer their quotient values to the sink node).At timet, if the WSN can only aggregate a part of sensed data from its nodes, it will provide an approximated SUM, expressed in Sum
(
S
t
)
′. If it aggregates all sensed data in the WSN, it will get an accurate SUM, called Sum
(
S
t
).Definition 4 (ε-estimate).
Sum
(
S
t
)
′ is called an ε-estimate of Sum
(
S
t
) if |
(
Sum
(
S
t
)
′
-
Sum
(
S
t
)
)
/
Sum
(
S
t
)
|
≤
ε for any ε (ε
≥
0).Definition 5 (reliability).
For a given network andε (ε
≥
0), reliability is the probability of that Sum
(
S
t
)
′ is the ε-estimate of Sum
(
S
t
) [20].Definition 6 (η).
For a given network andε (ε
≥
0), η (0
≤
η
≤
1) is the lower bound of probability of that Sum
(
S
t
)
′ is the ε-estimate of Sum
(
S
t
); that is, η
≤
P
(
|
(
Sum
(
S
t
)
′
-
Sum
(
S
t
)
)
/
Sum
(
S
t
)
|
≤
ε
).Definition 7 (unbiased estimate).
Sum
(
S
t
)
′ is an unbiased estimate of Sum
(
S
t
) if the mathematical expectation of Sum
(
S
t
)
′ is equal to Sum
(
S
t
); that is, E
(
Sum
(
S
t
)
′
)
=
Sum
(
S
t
); otherwise Sum
(
S
t
)
′ is a biased estimator of Sum
(
S
t
).Definition 8 (round).
The amount of time from the sink node initiates a data collection command to all sensed data from SNs being sent to the sink node, no matter how long it will last. This amount of time is called one round.


## 2.2. Reliability-Oriented Local-Area Model

In this section, we model a WSN as a network with growth and preferential attachment and propose an evolution model ROLM with high reliability. Different from [9], the WSN evolving from ROLM includes three kinds of links. They are the bidirectional link between CHs (CH↔CH), the directional link from SN to CH (SN→CH), and the bidirectional link between SNs (SN↔SN). For CH
i, let k
c
i be the current degree that is the total number of links pointing to CH
i from other nodes, and let E
c
i be its initial energy value. And for a SN
i, provide that k
s
i is the degree that is the total number of links pointing to SN
i from other SNs and E
s
i represents the initial energy value of SN
i. Define that E
c
i is a random variable following the uniform distribution ρ
(
E
c
) in the interval [
E
min
⁡
c
,
E
max
⁡
c
] and E
s
i is a random variable following the uniform distribution ρ
(
E
s
) in the interval [
E
min
⁡
s
,
E
max
⁡
s
]. Set E
c
i as much larger than E
s
i. Here, E
max
⁡
c
≥
E
min
⁡
c
≥
E
max
⁡
s
≥
E
min
⁡
s, E
max
⁡
c is the maximum initial energy of CHs, and a CH with E
maxc could connect with less than k
max
⁡
c nodes. Similarly, E
max
⁡
s is the maximum initial energy of SNs, and the SN with E
maxs could connect with less than k
max
⁡
s SNs. Let k
max
⁡
c
i and k
max
⁡
s
i be the saturated degree of CH
i and SN
i respectively; then we define(1)
k
max
⁡
c
i
=
k
max
⁡
c
E
c
i
E
max
⁡
c
,
k
max
⁡
s
i
=
k
max
⁡
s
E
s
i
E
max
⁡
s
.The basic settings for ROLM can be described as  shown in Algorithm1.Algorithm 1
//defining the variables
C
H
i:
Var k
c
i, E
c
i
S
N
i:
Var k
s
i, E
s
i
Begain
/////////////////////////////////////////////////////
//the types of node in ROLM
Fori
=
1 to NumberOfNetworks do
{
probability P:
nodeKind =
= CH;
probability 1
-
P:
nodeKind =
= SN;
}
//initializing node energy
Fori
=
1 to NumberOfNetworks do
{
If nodeKind=
= CH
E
c
i
=
ρ
(
E
c
); //the initial energy value of C
H
i
Else if nodeKind=
= SN
E
s
i
=
ρ
(
E
s
);  //the initial energy value of S
N
i, and E
max
⁡
c
≥
E
min
⁡
c
≥
E
max
⁡
s
≥
E
min
⁡
s
}
//calculating the saturated degree ofC
H
i and S
N
i
Fori
=
1 to NumberOfNetworks do
{
k
max
⁡
c
i
=
k
max
⁡
c
E
c
i
E
max
⁡
c; //the saturated degree of C
H
i, and set the value of k
max
⁡
c to be 20
k
max
⁡
s
i
=
k
max
⁡
s
E
s
i
E
max
⁡
s; //the saturated degree of S
N
i, and set the value of k
max
⁡
s to be 7
}The growth in the WSN evolving from ROLM is starting with an existing network with a small number ofc
0 nodes (all of these c
0 nodes are connected with each other. As SNs connect to the sink node by CHs, there must be at least one CH among these c
0 nodes). Referring to the BA modeling method in complex networks, ROLM can be described as follows.(
a
)
At every step, a new-incoming node (CH or SN) connects to one node in an existing network. If the new-incoming node is a CH with energy valueE
c
i, it may connect to the other CHs within its local-area, while if the new-incoming node is a SN with energy value E
s
i, it may connect to a CH or a SN within its local-area. For a new-incoming CH, it enters the preexisting network with probability p (the probability p is the proportion of CHs in the WSN evolving from ROLM), as new-incoming nodes include CHs and SNs; thus the proportion of SNs in the WSN evolving from ROLM is (
1
-
p
), and the probability for a new-incoming SN entering the preexisting network is (
1
-
p
).
(
b
)
Preferential attachment: the new-incoming CH connects to a selected CH in the preexisting network, and the new-incoming SN connects to a selected CH or a SN from the preexisting network. In this case, as the node in WSNs has the constraints of energy and connectivity, it only communicates with one CH or SN in the local-area to avoid data redundancy. Firstly, we markC nodes randomly from the preexisting network as the local-area Φ. As the scale of local-area Φ is based on the new-incoming node’s communication range, and the directly connected nodes of each node are chosen from these C nodes, we set C
≥
max
⁡
{
k
max
⁡
s
,
k
max
⁡
c
}. Considering that nodes have constraints of energy and connectivity, and ROLM is trying to improve the reliability of the WSN for some aggregation operators, in the WSN evolving from ROLM, the new-incoming nodes (CHs or SNs) will connect to CH
i in the local-area Φ according to the probability ∏
c
i, and SN
i in the local-area Φ will be connected by new-incoming SNs according to the probability ∏
s
i:(2)
∏
c
i
=
E
r
c
i
k
c
i
/
ω
i
∑
j
∈
Φ
E
r
c
j
k
c
j
/
ω
j
(3)
∏
s
i
=
E
r
s
i
k
s
i
/
ω
i
∑
j
∈
Φ
E
r
s
j
k
s
j
/
ω
j
,
whereE
r
c
i and E
r
s
i are the residual energy of CH
i and SN
i.
Considering the fact that every link connected to nodei will consume some energy of node i, we simply define(4)
E
r
c
i
=
E
c
i
-
b
k
c
i
,
(5)
E
r
s
i
=
E
s
i
-
b
k
s
i
,
whereb is a constant and can be regarded as the energy consumed by every link. Formulas (4) and (5) mean that the closer the degree of node i is to k
max
⁡
c
i or k
max
⁡
s
i, the less the residual energy of the node i will be left. Replacing E
r
c
i and E
r
s
i with (4) and (5) in formulas (2) and (3), respectively, we can get(6)
∏
c
i
=
(
E
c
i
-
b
k
c
i
)
/
ω
i
∑
j
∈
Φ
(
E
c
j
-
b
k
c
j
)
/
ω
j
,
∏
s
i
=
(
E
s
i
-
b
k
s
i
)
/
ω
i
∑
j
∈
Φ
(
E
s
j
-
b
k
s
j
)
/
ω
j
.
(
c
)
After step (b), when a new-incoming SN enters into the preexisting network, and if the degree of an existingSN
i is k
s
i
<
k
max
⁡
s
i, return to step (b); otherwise remove SN
i from the local-area Φ; that is to say, a new node cannot connect to this SN
i even though SN
i is within the local-area Φ. When a new-incoming node (CH or SN) enters into the pre-existing network, if the degree of CH
i is k
c
i
<
(
k
max
⁡
c
i
-
1
) (it could avoid all these k
max
⁡
c
i nodes connected to one CH
i are SNs, and the new-incoming CH cannot joint into the pre-existing network as all CHs within the local-area Φ have reached their saturated degrees), and the new-incoming node is a SN, then return to step (b), otherwise remove CH
i from the local-area Φ; if the degree of CH
i is k
c
i
<
k
max
⁡
c
i, and the new-incoming node is a CH, then return to step (b), otherwise remove CH
i from the local-area Φ.The description of ROLM with pseudocode  is shown as in Pseudocode1.Pseudocode 1
//starting with an existing network with a small number ofc
0 nodes and at least one CH node among them
//using the Function_ROLM_Model to construct the WSN
Function_ROLM_Model
Begain
Form
=
1 to NumberOfNetworks do
{
//Firstly, we markC nodes randomly from the pre-existing network as the local-area Φ
local-areaΦ: C nodes, C
≥
max
⁡
{
k
max
⁡
s
,
k
max
⁡
c
}
If nodeKind=
= SN
{
For i
=
1 to C do
{
If k
s
i
≤
k
max
⁡
s
i
{
∏
s
i
=
E
r
s
i
k
s
i
/
ω
i
∑
j
∈
Φ
E
r
s
j
k
s
j
/
ω
j; //E
r
s
i is the residual energy of S
N
i, ω
i and ω
j are
the sink layer values of node i and node j
/
}
/
}
node(i) = max
⁡
(
∏
s
i
); //select the node with max probability ∏
s
i from the local-area Φ
CONNECT(node(m), node(i)); //connect node(m) & node(i), link(m
,
i)
E
r
s
i
=
E
s
i
-
b
k
s
i; //b is regarded as the energy consumed by every link
k
s
i
+
=
1;
/
}
Else if nodeKind=
= CH
{
For i
=
1 to C do
{
Ifk
c
i
<
(
k
max
⁡
c
i
-
1
) && nodeKind =
= CH
{
∏
c
i
=
E
r
c
i
k
c
i
/
ω
i
∑
j
∈
Φ
E
r
c
j
k
c
j
/
ω
j; //E
r
c
i is the residual energy of C
H
i. ω
i and ω
j are
the sink layer values of nodei and node j
/
}
/
}
Node(i) = max
⁡
(
∏
c
i
); //select the node with max probability ∏
s
i from the local-area Φ
CONNECT(node(m), node(i)); //connect node(m) & node(i
), link(m
,
i)
E
r
c
i
=
E
c
i
-
b
k
c
i; //b is regarded as the energy consumed by every link
k
c
i
+
=
1;
/
}
/
}
End_ROLMFor a WSN with a certain number of nodes, through the above three steps, the nodes in the WSN can be connected with each other. When the number of nodes is 5000,k
max
⁡
s
=
7, k
max
⁡
c
=
20, the topology graph is shown in Figure 1(a), and Figure 1(b) is an example for detailed topology of one cluster in Figure 1(a). The three steps of ROLM show that the probability of a new-incoming node connecting to a preexisting CH
i or SN
i not only depends on its current state: k
c
i  (or k
s
i) and ω
c
i  (or ω
s
i) but also has the constraint of k
c
i
<
k
max
⁡
c
i
≤
k
max
⁡
c (or k
s
i
<
k
max
⁡
s
i
≤
k
max
⁡
s), and k
c
i (k
s
i) depends on the node i’s initial energy. ROLM has considered the diversities of nodes and links and balanced the energy consumption globally by limiting the links to a CH and the links to a father SN. Furthermore, it also improves the reliability of WSNs for an aggregation operator (the smaller the ω
s
i is, the higher the reliability of WSNs will be, and it will be proved in the next section for SUM aggregation operator) without shortening the lifetime of the network. As high-reliability and energy efficiency are both critically important for most WSNs applications [26, 27], the WSN evolving from ROLM can perform more efficiently under such environment.Figure 1
The topology graph and subgraph of topology of the WSN, where nodes’ sizes represent their current degree, the nodes’ color reflects their community structure, nodes with the same color means that they have the same modularity, and the communication among them will be more frequent.
(a)
Topology graph
(b)
Subgraph of topology


## 3. Mathematic Principle ofη

Since this paper is dedicated to present an evolution model ROLM to improve the reliability of WSNs, in the following sections we analytically calculate the reliability of the WSN evolving from ROLM for SUM aggregation operator. Section2.2 shows that, when the number of network nodes is given, through the three steps in Section 2.2, we can connect these nodes to form a complete WSN. Here, we provide that the two kinds of nodes in the WSN are uniformly distributed in the monitoring environment and p is the proportion of CHs.LetN
t be the number of SNs in the WSN at time t. Let s
i (1
≤
i
≤
N
t) be the sensed data of SN
i at time t, and let S
t
=
{
s
1
,
s
2
,
…
s
N
t
} be the set of all sensed data in the WSN at time t. Since the value of sensed data is bounded, we use sup
⁡
(
S
t
) to denote the upper bound of all sensed data, and the metric of data depends on the category of sensors.From the analysis in Section2.2, except the sink node and the links between CHs and sink node, we can construct a WSN consisting of two kinds of nodes (CHs and SNs) and three kinds of links (CH↔CH, SN→CH, and SN↔SN). The WSN is divided into a number of clusters which are disjoined with each other, and a cluster consists of one CH and many SNs. Here, we define that the WSN is divided into n clusters. Let ω
=
max
⁡
{
ω
s
i
,
1
≤
i
≤
(
1
-
p
)
N
t
} be the maximum value of cluster layer of SNs at time t, and let m
1
,
m
2
,
m
3
,
…
,
m
ω be the numbers of SNs whose ω
s
i
=
1, ω
s
i
=
2
,
ω
s
i
=
3
,
…, and ω
s
i
=
ω at time t, respectively. Let S
t
,
1
=
{
s
t
,
1
1
,
s
t
,
1
2
,
s
t
,
1
3
,
…
,
s
t
,
1
m
1
} be the set of sensed data from SNs with ω
s
i
=
1 at time t, and let S
t
,
2
,
S
t
,
3
,
…
,
S
t
,
ω be the sets of sensed data from SNs with ω
s
i
=
2, SNs with ω
s
i
=
3
,
…, and SNs with ω
s
i
=
ω at time t, respectively. Then the relationship among S
t
,
S
t
,
1
,
S
t
,
2
,
S
t
,
3
,
…
,
S
t
,
ω can be described as S
t
,
1
⊆
S
t
,
S
t
,
2
⊆
S
t
,
S
t
,
3
⊆
S
t
…, S
t
,
ω
⊆
S
t, S
t
=
{
S
t
,
1
,
S
t
,
2
,
S
t
,
3
…
,
S
t
,
ω
}.As the WSN for practical applications is not ideal deterministic network model, a data transmission over the wireless link of the real WSN is successfully conducted with a certain probability [28]. Here, when the sink node initiating one time of data collecting at time t, we provide that a link SN→CH or SN↔SN is connected successfully with probability q. In our model, CHs’ initial energy is larger; we define that the timeout retransmission mechanism is used among CHs and sink node, and therefore data communications over CH↔CH links can be successfully conducted with probability 1.According to the above analysis, at timet, the sensed data of SNs with ω
s
i
=
1 will be sent successfully to the sink node with a certain probability q. Similarly, the sensed data from SNs with ω
s
i
=
2, SNs with ω
s
i
=
3
,
…, and SNs with ω
s
i
=
ω will be sent successfully to the sink node with the probabilities q
2
,
q
3
,
…
,
q
ω, respectively. To facilitate our research on data analysis, let B
(
q
)
,
B
(
q
2
)
,
B
(
q
3
)
,
…
,
B
(
q
ω
) be the set of sensed data that are sent successfully to the sink node from the SNs with ω
s
i
=
1, SNs with ω
s
i
=
2, SNs with ω
s
i
=
3
,
…, and SNs with ω
s
i
=
ω at time t respectively. In order to deliver the sensed data successfully to the sink node, the medium access schedule of our network model is similar to that in [29].In order to specifically study the reliability of the WSN, we take the SUM aggregation operator as an example (the other operator also can be got with the same processing method) and propose the concept of reliability andη parameter to measure the reliability of the WSN. Here, the accurate SUM of the WSN at time t is defined as Sum
(
S
t
)
=
∑
i
=
1
m
1
s
t
,
1
i
+
∑
i
=
1
m
2
s
t
,
2
i
+
∑
i
=
1
m
3
s
t
,
3
i
+
⋯
+
∑
i
=
1
m
ω
s
t
,
ω
i. In the next section, we will analyze the mathematic principle of η and study whether the approximated SUM can replace the accurate SUM, which is one of the basic requirements of researching on the reliability of the WSN. It also determines whether we need to measure the reliability of the WSN. After that, we will research on how to calculate the value of η and use it to measure the reliability of the WSN.


### 3.1. Estimator of Sum

As the definitions show above,S
t
,
1
,
S
t
,
2
,
S
t
,
3
,
…
,
S
t
,
ω are the sets of sensed data from SNs with ω
s
i
=
1, SNs with ω
s
i
=
2, SNs with ω
s
i
=
3
,
…, and SNs with ω
s
i
=
ω at time t, respectively, and B
(
q
)
,
B
(
q
2
)
,
B
(
q
3
)
,
…
,
B
(
q
ω
) are the sets of sensed data which are sent successfully to the sink node from SNs with ω
s
i
=
1, SNs with ω
s
i
=
2, SNs with ω
s
i
=
3
,
…, and SNs with ω
s
i
=
ω at time t, respectively. The approximated SUM is denoted by Sum
(
S
t
)
′, and Sum
(
S
t
)
′ can be computed by(7)
Sum
S
t
′
=
1
q
∑
s
t
,
1
i
∈
B
(
q
)
s
t
,
1
i
+
1
q
2
∑
s
t
,
1
i
∈
B
(
q
2
)
s
t
,
2
i
+
⋯
+
1
q
ω
∑
s
t
,
ω
i
∈
B
q
ω
s
t
,
ω
i
.According to the definition of unbiased estimate in Section2.1, the following Theorem 9 will show that Sum
(
S
t
)
′ is the unbiased estimator of Sum
(
S
t
).Theorem 9.
LetE
(
Sum
(
S
t
)
′
) be the expectation of Sum
(
S
t
)
′, and let Var
(
Sum
(
S
t
)
′
) be the variance. Then,(8)
E
(
Sum
S
t
′
)
=
Sum
(
S
t
)
Var
Sum
S
t
′
≤
sup
⁡
S
t

Sum
S
t
1
-
q
ω
q
ω
.Theorem 9 will be proved in Appendix A. It shows that the mathematic estimator of Sum
(
S
t
)
′ is the unbiased estimator of Sum
(
S
t
) and the upper bound of Var
(
Sum
(
S
t
)
′
) is inversely proportional to q. That is to say, with the increase of q, the upper bound of Var
(
Sum
(
S
t
)
′
) can be arbitrarily small. Reference [30] shows that, with q increasing, the relative error between Sum
(
S
t
)
′ and Sum
(
S
t
) gradually decreases, and if q is sufficiently large, this relative error can be arbitrarily small.


### 3.2. Calculation ofη

The steps of calculating the value ofη are(a)
proving thatSum
(
S
t
)
′ follows normal distribution;
(b)
transforming the normal distribution into standard normal distribution;
(c)
utilizing characteristics of standard normal distribution to calculate the value ofη.For anyi, let the variable Y
v
i (1
≤
v
≤
ω) denote the following equations:(9)
Y
1
i
=
s
t
,
1
i
if
s
t
,
1
i
∈
B
(
q
)
0
if
s
t
,
1
i
∉
B
(
q
)
⋮
Y
ω
i
=
s
t
,
ω
i
if
s
t
,
ω
i
∈
B
(
q
ω
)
0
if
s
t
,
ω
i
∉
B
(
q
ω
)
.There isSum
(
S
t
)
′
=
(
1
/
q
)
∑
s
t
,
1
i
∈
B
q
s
t
,
1
i
+
(
1
/
q
2
)
∑
s
t
,
1
i
∈
B
q
2
s
t
,
2
i
+
⋯
+
(
1
/
q
ω
)
∑
s
t
,
ω
i
∈
B
(
q
ω
)
s
t
,
ω
i. Firstly, we need to prove that Sum
(
S
t
)
′ follows normal distribution. In view of the linear combination of n independent normal distribution variables still follow normal distribution, through proving that the sum of sensed data of SNs with ω
s
i
=
1, the sum of sensed data of SNs with ω
s
i
=
2
,
…, and the sum of sensed data of SNs with ω
s
i
=
ω all follow normal distribution to prove that Sum
(
S
t
)
′ follows normal distribution. Reference [31] shows that, if sensed data from SNs with ω
s
i
=
v
(
1
≤
v
≤
ω
) is conformed to Lyapunov condition, the sum of sensed data from SNs with ω
s
i
=
v will meet the application conditions of central limit theorem; that is, the sum of sensed data from SNs with ω
s
i
=
v will follow normal distribution. And Theorem 10 proves that sensed data from SNs with ω
s
i
=
1, SNs with ω
s
i
=
2
,
…, and SNs with ω
s
i
=
ω are all conformed to Lyapunov condition, respectively.Theorem 10.
Theseω groups of sequence of random variables Y
v
i
(
1
≤
v
≤
ω
) satisfy Lyapunov condition; that is, ∃
ξ
v
>
0 satisfies the following:(10)
lim
m
v
→
∞
1
s
m
v
2
+
ξ
v
∑
i
=
1
m
v
E
Y
v
i
-
μ
v
i
2
+
ξ
v
=
0
,where 1
≤
v
≤
ω, m
v is the number of sensed data from SNs with cluster layer v at time t, and s
m
v
2
=
∑
i
=
1
m
v
σ
v
i, and for all i
(
1
≤
i
≤
m
v
) there are μ
v
i
=
E
(
Y
v
i
) and σ
v
i
=
Var
(
Y
v
i
).The proof for Theorem10 will be given in Appendix B [31]. Theorem 10 shows that these ω groups of random variable sequences Y
v
i (1
≤
v
≤
ω) satisfy Lyapunov conditions. That is, the sum of sensed data from SNs with ω
s
i
=
v
(
1
≤
v
≤
ω
)
Sum
(
S
t
,
v
)
′
=
∑
i
=
1
m
v
Y
v
i follows normal distribution. As the successful transmissions of the sensed data from SNs with ω
s
i
=
v to the sink node are independent of other SNs with ω
s
i, Sum
(
S
t
)
′ is the sum of these ω independent variable normal distributions Sum
(
S
t
,
v
)
′. Thus Sum
(
S
t
)
′ follows normal distribution. For a given relative error limit ε, the following Theorem 11 describes how to calculate the η of the WSN.Theorem 11.
Defineδ
=
1
-
η, and ϕ
δ
/
2 is the δ
/
2 quantile of standardized normal distribution, if ϕ
δ
/
2 satisfies (11)
ϕ
δ
/
2
2
≤
q
ω
inf
⁡
(
N
t
)
inf
⁡
(
S
t
)
ε
2
(
1
-
q
ω
)
sup
⁡
(
S
t
)
.Then, the probability that the relative error betweenSum
(
S
t
)
′ and Sum
(
S
t
) satisfies the given error limit ε will be equal to or greater than η; that is,(12)
Pr
⁡
Sum
S
t
′
-
Sum
(
S
t
)
Sum
(
S
t
)
≤
ε
≥
η
.We will prove Theorem 11 in Appendix C [32]. In Theorem 11, η is an important parameter which could measure the reliability of the WSN in our research. Combining with the above analysis, we can conclude that the problem of the calculation of η can be described as follows.Input.
(
1
)
S
t
,
1
=
{
s
t
,
1
1
,
s
t
,
1
2
,
s
t
,
1
3
,
…
,
s
t
,
1
m
1
}, S
t
,
2
,
S
t
,
3
,
…
,
S
t
,
ω;I
n
p
u
t
:
(
2
)   ε (ε
≥
0), ω and q;I
n
p
u
t
:
(
3
) SUM aggregation operator.Output. The value of η.


## 3.1. Estimator of Sum

As the definitions show above,S
t
,
1
,
S
t
,
2
,
S
t
,
3
,
…
,
S
t
,
ω are the sets of sensed data from SNs with ω
s
i
=
1, SNs with ω
s
i
=
2, SNs with ω
s
i
=
3
,
…, and SNs with ω
s
i
=
ω at time t, respectively, and B
(
q
)
,
B
(
q
2
)
,
B
(
q
3
)
,
…
,
B
(
q
ω
) are the sets of sensed data which are sent successfully to the sink node from SNs with ω
s
i
=
1, SNs with ω
s
i
=
2, SNs with ω
s
i
=
3
,
…, and SNs with ω
s
i
=
ω at time t, respectively. The approximated SUM is denoted by Sum
(
S
t
)
′, and Sum
(
S
t
)
′ can be computed by(7)
Sum
S
t
′
=
1
q
∑
s
t
,
1
i
∈
B
(
q
)
s
t
,
1
i
+
1
q
2
∑
s
t
,
1
i
∈
B
(
q
2
)
s
t
,
2
i
+
⋯
+
1
q
ω
∑
s
t
,
ω
i
∈
B
q
ω
s
t
,
ω
i
.According to the definition of unbiased estimate in Section2.1, the following Theorem 9 will show that Sum
(
S
t
)
′ is the unbiased estimator of Sum
(
S
t
).Theorem 9.
LetE
(
Sum
(
S
t
)
′
) be the expectation of Sum
(
S
t
)
′, and let Var
(
Sum
(
S
t
)
′
) be the variance. Then,(8)
E
(
Sum
S
t
′
)
=
Sum
(
S
t
)
Var
Sum
S
t
′
≤
sup
⁡
S
t

Sum
S
t
1
-
q
ω
q
ω
.Theorem 9 will be proved in Appendix A. It shows that the mathematic estimator of Sum
(
S
t
)
′ is the unbiased estimator of Sum
(
S
t
) and the upper bound of Var
(
Sum
(
S
t
)
′
) is inversely proportional to q. That is to say, with the increase of q, the upper bound of Var
(
Sum
(
S
t
)
′
) can be arbitrarily small. Reference [30] shows that, with q increasing, the relative error between Sum
(
S
t
)
′ and Sum
(
S
t
) gradually decreases, and if q is sufficiently large, this relative error can be arbitrarily small.


## 3.2. Calculation ofη

The steps of calculating the value ofη are(a)
proving thatSum
(
S
t
)
′ follows normal distribution;
(b)
transforming the normal distribution into standard normal distribution;
(c)
utilizing characteristics of standard normal distribution to calculate the value ofη.For anyi, let the variable Y
v
i (1
≤
v
≤
ω) denote the following equations:(9)
Y
1
i
=
s
t
,
1
i
if
s
t
,
1
i
∈
B
(
q
)
0
if
s
t
,
1
i
∉
B
(
q
)
⋮
Y
ω
i
=
s
t
,
ω
i
if
s
t
,
ω
i
∈
B
(
q
ω
)
0
if
s
t
,
ω
i
∉
B
(
q
ω
)
.There isSum
(
S
t
)
′
=
(
1
/
q
)
∑
s
t
,
1
i
∈
B
q
s
t
,
1
i
+
(
1
/
q
2
)
∑
s
t
,
1
i
∈
B
q
2
s
t
,
2
i
+
⋯
+
(
1
/
q
ω
)
∑
s
t
,
ω
i
∈
B
(
q
ω
)
s
t
,
ω
i. Firstly, we need to prove that Sum
(
S
t
)
′ follows normal distribution. In view of the linear combination of n independent normal distribution variables still follow normal distribution, through proving that the sum of sensed data of SNs with ω
s
i
=
1, the sum of sensed data of SNs with ω
s
i
=
2
,
…, and the sum of sensed data of SNs with ω
s
i
=
ω all follow normal distribution to prove that Sum
(
S
t
)
′ follows normal distribution. Reference [31] shows that, if sensed data from SNs with ω
s
i
=
v
(
1
≤
v
≤
ω
) is conformed to Lyapunov condition, the sum of sensed data from SNs with ω
s
i
=
v will meet the application conditions of central limit theorem; that is, the sum of sensed data from SNs with ω
s
i
=
v will follow normal distribution. And Theorem 10 proves that sensed data from SNs with ω
s
i
=
1, SNs with ω
s
i
=
2
,
…, and SNs with ω
s
i
=
ω are all conformed to Lyapunov condition, respectively.Theorem 10.
Theseω groups of sequence of random variables Y
v
i
(
1
≤
v
≤
ω
) satisfy Lyapunov condition; that is, ∃
ξ
v
>
0 satisfies the following:(10)
lim
m
v
→
∞
1
s
m
v
2
+
ξ
v
∑
i
=
1
m
v
E
Y
v
i
-
μ
v
i
2
+
ξ
v
=
0
,where 1
≤
v
≤
ω, m
v is the number of sensed data from SNs with cluster layer v at time t, and s
m
v
2
=
∑
i
=
1
m
v
σ
v
i, and for all i
(
1
≤
i
≤
m
v
) there are μ
v
i
=
E
(
Y
v
i
) and σ
v
i
=
Var
(
Y
v
i
).The proof for Theorem10 will be given in Appendix B [31]. Theorem 10 shows that these ω groups of random variable sequences Y
v
i (1
≤
v
≤
ω) satisfy Lyapunov conditions. That is, the sum of sensed data from SNs with ω
s
i
=
v
(
1
≤
v
≤
ω
)
Sum
(
S
t
,
v
)
′
=
∑
i
=
1
m
v
Y
v
i follows normal distribution. As the successful transmissions of the sensed data from SNs with ω
s
i
=
v to the sink node are independent of other SNs with ω
s
i, Sum
(
S
t
)
′ is the sum of these ω independent variable normal distributions Sum
(
S
t
,
v
)
′. Thus Sum
(
S
t
)
′ follows normal distribution. For a given relative error limit ε, the following Theorem 11 describes how to calculate the η of the WSN.Theorem 11.
Defineδ
=
1
-
η, and ϕ
δ
/
2 is the δ
/
2 quantile of standardized normal distribution, if ϕ
δ
/
2 satisfies (11)
ϕ
δ
/
2
2
≤
q
ω
inf
⁡
(
N
t
)
inf
⁡
(
S
t
)
ε
2
(
1
-
q
ω
)
sup
⁡
(
S
t
)
.Then, the probability that the relative error betweenSum
(
S
t
)
′ and Sum
(
S
t
) satisfies the given error limit ε will be equal to or greater than η; that is,(12)
Pr
⁡
Sum
S
t
′
-
Sum
(
S
t
)
Sum
(
S
t
)
≤
ε
≥
η
.We will prove Theorem 11 in Appendix C [32]. In Theorem 11, η is an important parameter which could measure the reliability of the WSN in our research. Combining with the above analysis, we can conclude that the problem of the calculation of η can be described as follows.Input.
(
1
)
S
t
,
1
=
{
s
t
,
1
1
,
s
t
,
1
2
,
s
t
,
1
3
,
…
,
s
t
,
1
m
1
}, S
t
,
2
,
S
t
,
3
,
…
,
S
t
,
ω;I
n
p
u
t
:
(
2
)   ε (ε
≥
0), ω and q;I
n
p
u
t
:
(
3
) SUM aggregation operator.Output. The value of η.


## 4. The Degree Distribution of Nodes

To achieve a better understanding of the considered model, in this section, ROLM will be analyzed in comparison with the model in [9]. When we apply the preferential attachment strategy of [9] to the network evolution, the new-incoming node (CH or SN) will connect to CH
i in the local-area Φ according to the probability ∏
c
i
′, and SN
i in the local-area Φ will be connected by a new-incoming SN according to the probability ∏
s
i
′:(13)
∏
c
i
′
=
(
E
c
i
-
b
k
c
i
)
·
k
c
i
∑
j
∈
Φ
(
E
c
j
-
b
k
c
j
)
·
k
c
j
,
∏
s
i
′
=
(
E
s
i
-
b
k
s
i
)
·
k
s
i
∑
j
∈
Φ
(
E
s
j
-
b
k
s
j
)
·
k
s
j
.Hereb is a constant and can be regarded as the energy consumed by every link. Considering that a small number of CHs would make lots of SNs connected to them and large number of CHs will waste the network resource, this paper will control the number of CHs in a low proportion. In order to compare these two evolution models fairly, in our experiment, all parameters are set in the same way in [9], and set the number of WSN nodes to be 5000, k
max
⁡
s
=
7, k
max
⁡
c
=
20, p
=
0.1, ρ
(
E
c
)
~
U
[
0.7,1
], ρ
(
E
s
)
~
U
[
0.3,0.7
]. Then we will use the evolution strategy of ROLM and the evolution strategy of [9] to connect the nodes and define that there are two kinds of nodes and three kinds of links in this WSN. Next, we will focus on the cumulative degree distribution log
⁡
10
(
P
(
k
)
) of nodes in WSNs evolving from ROLM and [9]. To find the cumulative degree distribution log
⁡
10
(
P
(
k
)
), we first need to do degree statistics (i.e., get the probability of a node with k links). The statistical result is shown as in Figure 2.Figure 2
The cumulative degree distributionlog
⁡
10
(
P
(
k
)
) of nodes in WSNs evolving from ROLM and [9].
(a)
(b)
(c)
(d)
(e)
(f)Figure2 shows the statistical results of C
=
25, C
=
35, and C
=
45 for WSNs evolving from ROLM and [9], respectively. The left and right three figures in Figure 2 indicate that the change of local-area scale C does not cause the cumulative degree distribution to change greatly. For the WSN evolving from ROLM, the slopes of fitting curves for these three C are within [−2.5, −2]. And for [9], the slopes of fitting curves are within [−3.6, −3.2]. That is, in these two evolution models, the scale of local-area C has a weak effect on the cumulative degree distribution.On the other hand, the six constant variables of the above six fitting curves exhibit that the power-law fitting of the WSN evolving from ROLM is better than that of [9], the WSN evolving from ROLM follows a power-law distribution that can be found generally in the so-called scale-free networks, and the power-law features of the WSN evolving from ROLM are more obvious than that of [9]. The six figures in Figure 2 could also reveal the proportion of the nodes (SNs who are father nodes and CHs) with high degree and low degree. There are a low proportion of nodes with high degree and the proportion of nodes with low degree is large. And the degree of most of the nodes k
c
i (or k
s
i) is far smaller than their maximum degree k
max
⁡
c (or k
max
⁡
s), which could prevent the CHs and father SNs from consuming energy too quickly; then the lifetime of the WSN would be prolonged.


## 5. The Discussion of Network Performances

In this section, we will discuss the performance of WSNs evolving from ROLM and [9]. As our purpose is to give an evolution model which is reliability-oriented, we will first analyze the reliability of WSNs evolving from ROLM and [9]. Considering that the advantage of [9] is prolonging the lifetime of WSN, we also analyze the lifetime of WSNs evolving from ROLM and [9] in this section. Finally, we study the average length of shortest path of these two WSNs.


### 5.1. The Analysis of Reliability

In this set of experiments, all parameters are set as follows: the scale of network is to be[
0,6000
], the probability q locates within the interval [0.85, 0.9] [33], C
=
25, k
max
⁡
s
=
7, k
max
⁡
c
=
20, p
=
0.1, ρ
(
E
c
)
~
U
[
0.7,1
], ρ
(
E
s
)
~
U
[
0.3,0.7
]. As the other parameters of formula (11) are decided by the actual use of the WSN, and when we compare the reliability of the WSN evolving from ROLM with that of [9], these parameters have no effects on the comparative results if we set them in the same way. Therefore, we just choose an example setting for these experiments in this part. And for different network scales and q, we can get corresponding WSNs evolving from ROLM and [9] and the maximum value of cluster layer of SNs for these networks. Then, in combination with Section 3, we can calculate the reliability of the corresponding networks with different network scale and q. The results are shown in Figure 3 (for q
=
0.85) and Figure 4 (for q
=
0.9).Figure 3
The changing trend of reliability with the increase of network scale(
q
=
0.85
).
(a)
The changing trend of ROLM reliability
(b)
The changing trend of [9] reliabilityFigure 4
The changing trend of reliability with the increase of network scale(
q
=
0.9
).
(a)
The changing trend of ROLM reliability
(b)
The changing trend of [9] reliabilityFirstly, the four figures in Figures3 and 4 show that, with the increasing of network scale, the reliability of network presents a downward trend (not monotonously decreasing). As the CHs enter into the preexisting network in probability p and the new-incoming nodes will link to CH
i or SN
i in the local-area Φ in accordance with the probability ∏
c
i or ∏
s
i in the WSN evolving from ROLM and ∏
c
i
′ or ∏
s
i
′ in the WSN evolving from [9], WSNs evolving from ROLM or [9] are not unique. That is, every evolution may end with a different network, and this leads to the fluctuating in Figures 3 and 4. Secondly, for the same q and network scale, the WSN evolving from ROLM will get a higher reliability than that of [9], such that the reliability of the WSN evolving from ROLM is 0.857 when N
t
=
1000, q
=
0.85, while the reliability of [9] is only 0.0011. This is due to the difference between the preferential attachment principles of ROLM and [9]. Reference [9] only considers balancing energy consumption globally to prolong the lifetime of the WSN, while ROLM not only considers balancing energy consumption globally but also tries to improve the reliability of data aggregation. The experiment results shown in Figures 3 and 4 indicate that ROLM can improve the reliability of WSN significantly. Lastly, experiment results in Figures 3(a) and 4(a) show that ROLM can guarantee the WSN a higher reliability for small-scale WSN and large-scale WSN. Even under the conditions where N
t
=
20000, q
=
0.85, the reliability of the WSN evolving from ROLM can maintain about 0.6399.


### 5.2. Network Lifetime of ROLM

After discussing the reliability of the WSN evolving from ROLM, we will analyze the network lifetime of the WSN evolving from ROLM in this part. Same as Section5.1, here we will compare the lifetime of the WSN evolving from ROLM with that of [9]. According to the definition of round in Section 2.1, in order to facilitate the statistics of round, we define that all nodes will aggregate its own sensed data and the sensed data from other nodes with fixed-length l bits and then send it to its father node. According to [34], for one SN, the energy expenditure of sending 1-bit data is equal to that of executing 1000 commands. Therefore, here we just calculate the communication energy expenditure and ignore that of executing overhead. In this group’s experiments, assuming a node expends b energy to send a l bits packet, we set b
=
E
max
⁡
c
/
500. That is, the energy of each node decreases by b in every round. If a node has less than b energy, then we consider that the node and all its son nodes are dead (the sensed data of its son nodes need it to relay their sensed data). Except from the N
t
=
5000, the rest of other variables are set as in Section 5.1. Under the above assumptions, the number of nodes alive will decrease with the increase of network running rounds, and the comparing results of lifetimes of WSNs evolving from ROLM and [9] are shown in Figure 5.Figure 5
WSNs lifetimes in different network scale of 1000, 3000, and 5000.
(a)
Complete graph (N
t
=
1000)
(b)
Detailed graph (N
t
=
1000)
(c)
Complete graph (N
t
=
3000)
(d)
Detailed graph (N
t
=
3000)
(e)
Complete graph (N
t
=
5000)
(f)
Detailed graph (N
t
=
5000)There are three groups of number in Figure5; they are network lifetimes in different network scale of 1000, 3000, and 5000. From Figures 5(a), 5(c), and 5(e), we find that, under the same assumptions, WSNs evolving from ROLM and [9] have the same lifetime, the network lifetime of both WSNs evolving from ROLM and [9] is 438, and their initial time of attenuation is 125. That is, some nodes begin to die from the 125th round, and all nodes are dead in the 438th round. Both of them have set the same k
max
⁡
c and k
max
⁡
s to prolong the lifetime of network.Figures5(b), 5(d), and 5(f) are detailed graphs of one part from Figures 5(a), 5(c), and 5(e), respectively. These three figures reveal that the number of nodes alive in the WSN evolving from [9] decreased quickly and the number of death nodes in the 125th round is much larger than that of ROLM. For the network with scale of 1000, the number of alive nodes in the WSN evolving from ROLM is larger than or equal to that of [9] among the rounds within [
1,175
]. And for the network with scale of 5000, the number of alive nodes in the WSN evolving from ROLM is larger than or equal to that of [9] among the rounds within [
1
,
200
]. That is, the WSN evolving from ROLM is more energy-efficient than that of [9]. This is because [9] only considers the energy consumption of nodes and did not control the maximum value of nodes’ cluster layer, which leads to the result that the new-incoming nodes have a tendency to link to the SNs that are far away from the sink node which can increase the hops among any two nodes and energy consumption for processing data and finally decrease the energy efficient.The above two groups of experiments about the network reliability and the network lifetime prove that ROLM can ensure a higher reliability which is much larger than that of [9], ROLM can be used in larger-scale network where [9] could not, and the energy efficiency of the WSN evolving from ROLM among some rounds is better than that of [9].


### 5.3.L-The Average Length of Shortest Path

In the WSN, SNs collect and send data to their father nodes (SNs or CHs) and then forward them to the sink node via multihops, so all SNs or CHs who act as a father node play an important role in data collecting and transmitting. We use〈
L
〉-the average length of shortest path to measure the average hops among SNs and CHs for data processing; its calculation can be written as [23](14)
L
=
1
N
(
N
-
1
)
·
∑
i
≠
j
d
i
j
,where d
i
j is the length of shortest path between any two nodes (SNs or CHs) i and j, N is the number of nodes in the network, and d
i
j
=
+
∞ if there is no path between nodes i and j. Different from [9], considering that every path in the network can reflect the efficiency of the network, we use the d
i
j between every two nodes in the network to calculate the value of 〈
L
〉. The smaller 〈
L
〉 means fewer hops and less energy consumption for data processing.On the other hand, [9] just analyzed the relationships among p, C, and 〈
L
〉, and these can reflect the influences of p and C on 〈
L
〉 but cannot reflect the efficiency of the evolution models. Therefore, in this part, we study the relationship among the scale of network N, 〈
L
〉, and C (C
=
25 and C
=
35) for WSNs evolving from ROLM and [9] and fix ρ
(
E
c
)
~
U
[
0.7,1
], ρ
(
E
s
)
~
U
[
0.3,0.7
], k
max
⁡
s
=
7, k
max
⁡
c
=
20, p
=
0.1 (shown as in Figure 6).Figure 6
The plot of〈
L
〉-network scale with ρ
(
E
)
~
U, C
=
25 and 45 for WNSs evolving from ROLM and [9].
(a)
C
=
25
(b)
C
=
45From Figure6, we can find that, for each N, 〈
L
〉 of the WSN evolving from ROLM is smaller than that of [9] no matter whether C
=
25 (shown as in Figure 6(a)) or C
=
45 (shown as in Figure 6(b)), such that when N
=
2000 and C
=
25, there are 〈
L
〉
=
9.587719786 for the WSN evolving from ROLM and 〈
L
〉
=
42.89694797 for the WSN evolving from [9]. When N
=
2000 and C
=
45, there are 〈
L
〉
=
9.441435432 for the WSN evolving from ROLM and 〈
L
〉
=
59.72642678 for the WSN evolving from [9]. That means the number of hops among two nodes in the WSN evolving from ROLM is less than that in [9] which can ensure a better synchronization, and the energy consumption for data processing in the WSN evolving from ROLM is less than that of [9]. It also explains the results shown in Figure 5 in which the WSN evolving from ROLM has better energy efficiency than that of [9]. That is because we try to reduce the cluster layer in the WSN evolving from ROLM while [9] does not consider it.The two blue lines in Figure6 indicate that the slopes of blue lines decrease with the increase of N (when N
>
1000), and the red lines do not have this phenomenon. That is, the WSN evolving from ROLM has more obvious small world characteristic than that of [9]. For different values of C, the change extent of 〈
L
〉 in the WSN evolving from ROLM is weaker than that in the WSN evolving from [9], which means that C has a weak effect on the WSN evolving from ROLM. Because [9] only considers the energy of nodes to evolve the WSN, for big C, the new-incoming node will tend to connect to the preexisting node whose residual energy is larger (no matter how many its cluster layers), and the change of C affects the 〈
L
〉 of the WSN evolving from [9].The above analysis and Section4 show that the WSN evolving from ROLM has steadier complex network features than that of [9].


## 5.1. The Analysis of Reliability

In this set of experiments, all parameters are set as follows: the scale of network is to be[
0,6000
], the probability q locates within the interval [0.85, 0.9] [33], C
=
25, k
max
⁡
s
=
7, k
max
⁡
c
=
20, p
=
0.1, ρ
(
E
c
)
~
U
[
0.7,1
], ρ
(
E
s
)
~
U
[
0.3,0.7
]. As the other parameters of formula (11) are decided by the actual use of the WSN, and when we compare the reliability of the WSN evolving from ROLM with that of [9], these parameters have no effects on the comparative results if we set them in the same way. Therefore, we just choose an example setting for these experiments in this part. And for different network scales and q, we can get corresponding WSNs evolving from ROLM and [9] and the maximum value of cluster layer of SNs for these networks. Then, in combination with Section 3, we can calculate the reliability of the corresponding networks with different network scale and q. The results are shown in Figure 3 (for q
=
0.85) and Figure 4 (for q
=
0.9).Figure 3
The changing trend of reliability with the increase of network scale(
q
=
0.85
).
(a)
The changing trend of ROLM reliability
(b)
The changing trend of [9] reliabilityFigure 4
The changing trend of reliability with the increase of network scale(
q
=
0.9
).
(a)
The changing trend of ROLM reliability
(b)
The changing trend of [9] reliabilityFirstly, the four figures in Figures3 and 4 show that, with the increasing of network scale, the reliability of network presents a downward trend (not monotonously decreasing). As the CHs enter into the preexisting network in probability p and the new-incoming nodes will link to CH
i or SN
i in the local-area Φ in accordance with the probability ∏
c
i or ∏
s
i in the WSN evolving from ROLM and ∏
c
i
′ or ∏
s
i
′ in the WSN evolving from [9], WSNs evolving from ROLM or [9] are not unique. That is, every evolution may end with a different network, and this leads to the fluctuating in Figures 3 and 4. Secondly, for the same q and network scale, the WSN evolving from ROLM will get a higher reliability than that of [9], such that the reliability of the WSN evolving from ROLM is 0.857 when N
t
=
1000, q
=
0.85, while the reliability of [9] is only 0.0011. This is due to the difference between the preferential attachment principles of ROLM and [9]. Reference [9] only considers balancing energy consumption globally to prolong the lifetime of the WSN, while ROLM not only considers balancing energy consumption globally but also tries to improve the reliability of data aggregation. The experiment results shown in Figures 3 and 4 indicate that ROLM can improve the reliability of WSN significantly. Lastly, experiment results in Figures 3(a) and 4(a) show that ROLM can guarantee the WSN a higher reliability for small-scale WSN and large-scale WSN. Even under the conditions where N
t
=
20000, q
=
0.85, the reliability of the WSN evolving from ROLM can maintain about 0.6399.


## 5.2. Network Lifetime of ROLM

After discussing the reliability of the WSN evolving from ROLM, we will analyze the network lifetime of the WSN evolving from ROLM in this part. Same as Section5.1, here we will compare the lifetime of the WSN evolving from ROLM with that of [9]. According to the definition of round in Section 2.1, in order to facilitate the statistics of round, we define that all nodes will aggregate its own sensed data and the sensed data from other nodes with fixed-length l bits and then send it to its father node. According to [34], for one SN, the energy expenditure of sending 1-bit data is equal to that of executing 1000 commands. Therefore, here we just calculate the communication energy expenditure and ignore that of executing overhead. In this group’s experiments, assuming a node expends b energy to send a l bits packet, we set b
=
E
max
⁡
c
/
500. That is, the energy of each node decreases by b in every round. If a node has less than b energy, then we consider that the node and all its son nodes are dead (the sensed data of its son nodes need it to relay their sensed data). Except from the N
t
=
5000, the rest of other variables are set as in Section 5.1. Under the above assumptions, the number of nodes alive will decrease with the increase of network running rounds, and the comparing results of lifetimes of WSNs evolving from ROLM and [9] are shown in Figure 5.Figure 5
WSNs lifetimes in different network scale of 1000, 3000, and 5000.
(a)
Complete graph (N
t
=
1000)
(b)
Detailed graph (N
t
=
1000)
(c)
Complete graph (N
t
=
3000)
(d)
Detailed graph (N
t
=
3000)
(e)
Complete graph (N
t
=
5000)
(f)
Detailed graph (N
t
=
5000)There are three groups of number in Figure5; they are network lifetimes in different network scale of 1000, 3000, and 5000. From Figures 5(a), 5(c), and 5(e), we find that, under the same assumptions, WSNs evolving from ROLM and [9] have the same lifetime, the network lifetime of both WSNs evolving from ROLM and [9] is 438, and their initial time of attenuation is 125. That is, some nodes begin to die from the 125th round, and all nodes are dead in the 438th round. Both of them have set the same k
max
⁡
c and k
max
⁡
s to prolong the lifetime of network.Figures5(b), 5(d), and 5(f) are detailed graphs of one part from Figures 5(a), 5(c), and 5(e), respectively. These three figures reveal that the number of nodes alive in the WSN evolving from [9] decreased quickly and the number of death nodes in the 125th round is much larger than that of ROLM. For the network with scale of 1000, the number of alive nodes in the WSN evolving from ROLM is larger than or equal to that of [9] among the rounds within [
1,175
]. And for the network with scale of 5000, the number of alive nodes in the WSN evolving from ROLM is larger than or equal to that of [9] among the rounds within [
1
,
200
]. That is, the WSN evolving from ROLM is more energy-efficient than that of [9]. This is because [9] only considers the energy consumption of nodes and did not control the maximum value of nodes’ cluster layer, which leads to the result that the new-incoming nodes have a tendency to link to the SNs that are far away from the sink node which can increase the hops among any two nodes and energy consumption for processing data and finally decrease the energy efficient.The above two groups of experiments about the network reliability and the network lifetime prove that ROLM can ensure a higher reliability which is much larger than that of [9], ROLM can be used in larger-scale network where [9] could not, and the energy efficiency of the WSN evolving from ROLM among some rounds is better than that of [9].


## 5.3.L-The Average Length of Shortest Path

In the WSN, SNs collect and send data to their father nodes (SNs or CHs) and then forward them to the sink node via multihops, so all SNs or CHs who act as a father node play an important role in data collecting and transmitting. We use〈
L
〉-the average length of shortest path to measure the average hops among SNs and CHs for data processing; its calculation can be written as [23](14)
L
=
1
N
(
N
-
1
)
·
∑
i
≠
j
d
i
j
,where d
i
j is the length of shortest path between any two nodes (SNs or CHs) i and j, N is the number of nodes in the network, and d
i
j
=
+
∞ if there is no path between nodes i and j. Different from [9], considering that every path in the network can reflect the efficiency of the network, we use the d
i
j between every two nodes in the network to calculate the value of 〈
L
〉. The smaller 〈
L
〉 means fewer hops and less energy consumption for data processing.On the other hand, [9] just analyzed the relationships among p, C, and 〈
L
〉, and these can reflect the influences of p and C on 〈
L
〉 but cannot reflect the efficiency of the evolution models. Therefore, in this part, we study the relationship among the scale of network N, 〈
L
〉, and C (C
=
25 and C
=
35) for WSNs evolving from ROLM and [9] and fix ρ
(
E
c
)
~
U
[
0.7,1
], ρ
(
E
s
)
~
U
[
0.3,0.7
], k
max
⁡
s
=
7, k
max
⁡
c
=
20, p
=
0.1 (shown as in Figure 6).Figure 6
The plot of〈
L
〉-network scale with ρ
(
E
)
~
U, C
=
25 and 45 for WNSs evolving from ROLM and [9].
(a)
C
=
25
(b)
C
=
45From Figure6, we can find that, for each N, 〈
L
〉 of the WSN evolving from ROLM is smaller than that of [9] no matter whether C
=
25 (shown as in Figure 6(a)) or C
=
45 (shown as in Figure 6(b)), such that when N
=
2000 and C
=
25, there are 〈
L
〉
=
9.587719786 for the WSN evolving from ROLM and 〈
L
〉
=
42.89694797 for the WSN evolving from [9]. When N
=
2000 and C
=
45, there are 〈
L
〉
=
9.441435432 for the WSN evolving from ROLM and 〈
L
〉
=
59.72642678 for the WSN evolving from [9]. That means the number of hops among two nodes in the WSN evolving from ROLM is less than that in [9] which can ensure a better synchronization, and the energy consumption for data processing in the WSN evolving from ROLM is less than that of [9]. It also explains the results shown in Figure 5 in which the WSN evolving from ROLM has better energy efficiency than that of [9]. That is because we try to reduce the cluster layer in the WSN evolving from ROLM while [9] does not consider it.The two blue lines in Figure6 indicate that the slopes of blue lines decrease with the increase of N (when N
>
1000), and the red lines do not have this phenomenon. That is, the WSN evolving from ROLM has more obvious small world characteristic than that of [9]. For different values of C, the change extent of 〈
L
〉 in the WSN evolving from ROLM is weaker than that in the WSN evolving from [9], which means that C has a weak effect on the WSN evolving from ROLM. Because [9] only considers the energy of nodes to evolve the WSN, for big C, the new-incoming node will tend to connect to the preexisting node whose residual energy is larger (no matter how many its cluster layers), and the change of C affects the 〈
L
〉 of the WSN evolving from [9].The above analysis and Section4 show that the WSN evolving from ROLM has steadier complex network features than that of [9].


## 6. Conclusions

Consider large-scale WSNs have showed many complex features and an appropriate evolution model is very necessary for improving the performances of WSNs. In this paper, we are trying to build an evolution model which could evolve a WSN with high reliability and find out a way to measure the reliability of network. Describing the WSN as a model with two kinds of nodes and three kinds of links, we proposed a reliability-oriented large-scale model (ROLM) to improve the reliability of the WSN for some aggregation operators and presented the reliability parameterη to measure the reliability of network for SUM aggregation operator. After proving the mathematical rationality of parameter η theoretically and deriving the calculating method of η, we use η as one of performance metrics of WSNs.The analysis of degree distribution of nodes shows that both of WSNs evolving from ROLM and [9] follow a power-law distribution and ROLM has a more obvious scale-free characteristic. From the experiments, we can find that, for a specific network scale, the reliability of the WSN evolving from ROLM is higher than that of [9]; for example, when q
=
0.85, the evolution model in [9] is unusable when the network scale is larger than 1000 nodes, while ROLM can ensure the reliability of the WSN to be 0.6399 even with 20000 nodes in the network. On the other hand, the experiment results also show that ROLM balanced energy consumption by limiting the connectivity of nodes to prolong the life of the network, and the WSN evolving from ROLM achieves the same long lifetime with that of [9]. Within many rounds, the energy efficiency of the WSN evolving from ROLM is better than that of [9]. Lastly, we also give experiments to analyze the average length of shortest path of WSNs evolving from ROLM and [9]. The results indicate that the hops among two nodes in the WSN evolving from ROLM are fewer than those in [9] which can ensure a better synchronization, and the energy consumption for data processing in the WSN evolving from ROLM is less than that of [9]. The experiments about the degree distribution and the average length of shortest path show that the WSN evolving from ROLM has steadier complex network features than that of [9]. And the experiments about the network reliabilities and lifetimes prove that the energy efficiency of the WSN evolving from ROLM within some rounds is better than that of [9], ROLM can ensure a higher reliability which is much larger than that of [9], and ROLM can be used in larger-scale network where [9] could not be.



---

*Source: 923692-2015-03-29.xml*