# A Topology Evolution Model Based on Revised PageRank Algorithm and Node Importance for Wireless Sensor Networks

Authors: Xiaogang Qi; Lifang Liu; Guoyong Cai; Mande Xie
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Wireless sensor network (WSN) is a classical self-organizing communication network, and its topology evolution currently becomes one of the attractive issues in this research field. Accordingly, the problem is divided into two subproblems: one is to design a new preferential attachment method and the other is to analyze the dynamics of the network topology evolution. To solve the first subproblem, a revised PageRank algorithm, called Con-rank, is proposed to evaluate the node importance upon the existing node contraction, and then a novel preferential attachment is designed based on the node importance calculated by the proposed Con-rank algorithm. To solve the second one, we firstly analyze the network topology evolution dynamics in a theoretical way and then simulate the evolution process. Theoretical analysis proves that the network topology evolution of our model agrees with power-law distribution, and simulation results are well consistent with our conclusions obtained from the theoretical analysis and simultaneously show that our topology evolution model is superior to the classic BA model in the average path length and the clustering coefficient, and the network topology is more robust and can tolerate the random attacks.


---

## Body

## 1. Introduction

Wireless sensor network (WSN) consists of spatially distributed autonomous sensors to monitor physical or environmental conditions, such as temperature, sound, vibration, pressure, motion, or pollutants, and to cooperatively transmit their data through the network to a sink node. Today WSNs are more and more widely used in variety of industrial and consumer applications, such as industrial process monitoring and control, machine health monitoring, environment and habitat monitoring, health care applications, home automation, and traffic control [1].In military and warfare applications, WSNs are deployed in hostile monitoring environment, and the sensor node is of limited energy support. Energy exhaustion and natural damage of some sensor nodes often result in the failure of the whole networks. As a vital technique, the construction and control of the topology play an important role in conquering these problems in WSNs. The main purpose of construction and control of topology is to achieve a higher communication quality, energy utilization efficiency, and strong robustness topology.Complex network model becomes increasingly popular in the complex communication networks topology control and performance optimization. Complex network is the abstract description of the complex systems which emphasize characteristics of topology [2]. A complex system contains a mass of units which are considered as nodes, and the forces among units are considered as edges [3]. To achieve better performance and more robust topology against the attacks in the network, people need to better understand the complex network theory and the possible application scenarios in these fields [4]. With the development of WSN, small-world model [5] and scale-free model [4] are widely used to optimize the WSN’s topology.As one classical complex network model, small-world model has the shorter average path length and the larger clustering coefficient and also a few of short cuts, so this kind of network can be easily destroyed under the targeted attacks [6]. As another classical complex network model, scale-free model has the power-law node degree distribution characteristic and the better robustness against random attacks, because its physical topology is tightly associated with the evolution process, which depends on the mechanism of its growth and preferential attachment, and lots of researchers have contributed their works for improving the performance of the network topology [6, 7]. In this paper, our purpose is to propose a new topology control method which is based on the scale-free model, and its evolution process includes two aspects as follows.(1)
Growth: the scale of the network is expanding.(2)
Preferential attachment: the newly joined node is more inclined to join those nodes with higher degree. Namely, the rich become richer.It is generally known that the preferential attachment is the most important one because it provides the principal rules about how a new node connects to the previous network topology and which node should be the potential candidate node to be connected. To achieve better performance of the network, we aim to revise the preferential attachment method and to consider more details for selecting the candidate node from the existing topology and connecting to the new node. PageRank algorithm is a method for node ranking in a network and also for evaluating the node’s importance in some application scenarios, so some revised PageRank algorithms were proposed to evaluate the node importance and select the important candidate nodes, and also some detailed rules were considered in the proposed algorithms [8–10]. However, we can see that these preferential attachment rules only concern more node’s degree.In some challenging applications, there are lots of nodes with same degree, which is not sufficient to make a rational decision. So some of the background information, such as location and flow, was taken into account to design the PageRank-based algorithms. Dorogovtsev showed that main properties of scale-free evolving networks may be described in frames of a simple continuous approach and also obtained the scaling relations for networks with nonlinear, accelerating growth and described the temporal evolution of arising distributions [11]. Unlike the well-studied models of growing networks, where the dominant dynamics consists of insertions like nodes and connections, and rewiring of existing links, Sarshar studied the scale-free evolving networks application in ad hoc network, where one also has to contend with rapid and random deletions of existing nodes (and the associated links); the dynamics discovered in the paper can be used to craft protocols for designing highly dynamic peer-to-peer networks and also to account for the power-law exponents observed in existing popular services [12]. However, the above algorithms missed some inner relationships, and the transform possibility matrix holds the same value for every link, which will be revised in our model.In this paper, we introduce node degree, centrality, and betweenness to revise the PageRank algorithm to evaluate the node importance of the WSNs, and a dynamic transmission matrix is built up; these will be helpful to form the new preferential attachment rules to select a suitable candidate node to be connected to the newest node. Thus, the robustness and survivability of WSNs are enhanced to some extent.The rest of the paper is organized as follows. Section2 introduces basic definitions of complex networks model and the limitations of the existing PageRank Algorithm. Con-rank node importance evaluation algorithm is proposed in Section 3; Section 4 proposes the new rule for topology evolution based on Con-rank algorithm; finally, the simulation results and conclusions will be shown in Section 5.


## 2. Complex Networks Model and PageRank Algorithm

In this section, we formally describe the complex networks and the PageRank algorithm in detail, which is the basis of our node importance evaluation algorithm and topology evolution.


### 2.1. Complex Networks Model

Complex networks can be modeled by graphG=(V,E), where G is a nondirection connected graph with n nodes and m edges. V={v1,v2,…,vn} is the set of nodes and E={e1,e2,…,em}⊆V×V represents the set of edges. H=[hij] is adjacent matrix of G with n rows and n columns, and the detailed definition of hij in H is shown as follows:(1)hij=1,if  there  is  one  edge  between  nodesiandj0,if  there  is  no  edge  between  nodesiandj.At the same time, some terms to be used to evaluate the node importance are listed as follows.(i)
Degreeki. It is the number of edges connected to node i.(ii)
Shortest DistanceDij. It is the number of hops along the shortest path between node i and node j.(iii)
CentralityCi. It is the reciprocal of the total cumulative sum of the distance from all other nodes to node i; namely, Ci=1/∑k=1nDik.(iv)
BetweennessBi. It is a ratio of the number of the shortest paths through the node i to the total number of the shortest paths which include all the node pairs of a network.(v)
Largest Effective Component. It is the effective subgraph with the largest size in a network.


### 2.2. PageRank Algorithm

According to PageRank algorithm, a weight of each web page can be computed through iteration, which depends on weights of the pages connecting to this page. Here is the PageRank equation:(2)PRi=1-λn+λ∑j∈NiPRjNi,where N(i) indicates the set of pages destined for page i, and surfers connect to another page with probability 1-λ, and follow the links in current page with probability λ.


## 2.1. Complex Networks Model

Complex networks can be modeled by graphG=(V,E), where G is a nondirection connected graph with n nodes and m edges. V={v1,v2,…,vn} is the set of nodes and E={e1,e2,…,em}⊆V×V represents the set of edges. H=[hij] is adjacent matrix of G with n rows and n columns, and the detailed definition of hij in H is shown as follows:(1)hij=1,if  there  is  one  edge  between  nodesiandj0,if  there  is  no  edge  between  nodesiandj.At the same time, some terms to be used to evaluate the node importance are listed as follows.(i)
Degreeki. It is the number of edges connected to node i.(ii)
Shortest DistanceDij. It is the number of hops along the shortest path between node i and node j.(iii)
CentralityCi. It is the reciprocal of the total cumulative sum of the distance from all other nodes to node i; namely, Ci=1/∑k=1nDik.(iv)
BetweennessBi. It is a ratio of the number of the shortest paths through the node i to the total number of the shortest paths which include all the node pairs of a network.(v)
Largest Effective Component. It is the effective subgraph with the largest size in a network.


## 2.2. PageRank Algorithm

According to PageRank algorithm, a weight of each web page can be computed through iteration, which depends on weights of the pages connecting to this page. Here is the PageRank equation:(2)PRi=1-λn+λ∑j∈NiPRjNi,where N(i) indicates the set of pages destined for page i, and surfers connect to another page with probability 1-λ, and follow the links in current page with probability λ.


## 3. Con-Rank Node Importance Evaluation Algorithm for WSNs

It is known that PageRank algorithm is proposed for node ranking and importance evaluation in Internet, and its limitation is that it only depends on hyperlink relationship. We have improved the original PageRank algorithm and proposed a so-called “Con-rank algorithm,” which is based on node similarity and the characteristics of WSN. First, a transformation probability matrix is built up, namely, the probability of each node transforming data to its neighbors, in which the more similar the nodes are, the higher probability they will have. Second, the normalized centrality is used to revise the uniform distributed parameter in PageRank algorithm.


### 3.1. Basis of Node Contraction

Here, we use node contraction algorithm proposed in [13] to calculate contraction value and is further used to compute the node importance. Because the node position and the degree are taken into account at the same time, the node importance in the network can be obtained.Definition 1.
Node contraction: there areki nodes, which are directly connected with node vi, and these nodes are all replaced by a new node vi′. One extreme example is that it becomes one-node network when the central node of a star network is contracted.Definition 2.
The cohesion degree ofG is that ∂[G]=1/(n·l)=1/(n·(∑i≠j∈Vlij)/n(n-1))=(n-1)/∑i≠j∈Vlij, where n≥2 and lij is the shortest distance from node i to node j, when n=1, ∂=1. Obviously 0<∂≤1, and ∂ gets the maximal value 1 when there is only one node in the network. So network cohesion degree is decided by connection ability of nodes in network, and one assumes that the average shortest distance between a couple of nodes is l. In addition, the number of nodes n can also influence network cohesion degree.Definition 3.
The contraction value of nodevi is si=1-∂[G]/∂[G∗vi], where G∗vi indicates the graph after contraction of node vi.Hence, according to Definitions1 and 2, we get (3)si=1-∂G∂G∗vi=1-1/n·lG1/n-ki·lG∗vi=n·lG-n-ni·lG∗vin·lG,where l is the same as that mentioned in Definition 2 and ki is the same as that mentioned in Definition 1.


### 3.2. Node Contraction Algorithm

Detailed node contraction procedure is listed in Algorithm1, in which the contraction value of node vi can be obtained.Algorithm 1:Node contraction algorithm.
Input:   Adjacent matrix H
Output: Node contraction value si
(1) Compute the direct distance matrix of all pairs of nodesD=[ddij];
(2) Compute cohesion degree∂[G] of the initial network according to Definition 2;
(3)for  all  vi∈V  do
(4)Compute the shortest distance matrix Di after node contraction based on vi, and Di=[lij]n×n;
(5)Compute cohesion degree ∂G∗vi according to Definition 2;
(6)Compute si according to Definition 3.
(7)endIn Algorithm1, we firstly have to get the direct distance matrix D=[ddij]n×n from the adjacent matrix H=[hij] of G: (4)ddij=0,ifi=j1,ifi≠j,hij=1∞,ifi≠j,hij=0.Secondly, we should update the shortest distancelpq′ between any node pair (vp,vq)∈V×V. Let I={vk∈V∣ddki≠∞} be the set of all the neighbor nodes and itself and the contraction of vi equal to ddst=0, s,t∈I. The corresponding update operations are listed as follows:(1)
vp≠vi and vq≠vi;
(i)
lpi+liq=lpq; that is, vi is in the shortest path between vp and vq; then lpq′=lpq-2;(ii)
lpi+liq=lpq+1; that is, vi is in the suboptimal path between vp and vq; then lpq′=lpq-1;(iii)
lpi+liq≥lpq+2; then lpq′=lpq;(2)
vp=vi or vq=vi; then lpq′=lpq-1;(3)
vi=vp=vq; then lpq′=lpq=0.Finally, all the nodes inI are replaced by a new node vi′ but the links between any pair of nodes remain, and we can get Li=[lpq′] by deleting the relative rows and column of vi in [lpq′]. When calculating Li, only n(n-1)/2 pairs of nodes need to be calculated because G is an undirected graph.


### 3.3. Computing Transformation Probability Matrix

S
i
j
=
s
i
/
s
j is the similarity of vi and vj, where si and sj are the contraction value of vi and vj, respectively, and can be calculated according to (3). Furthermore, we can compute the transformation probability matrix T, and Tij=Sji/∑jSji and T should be normalized further.


### 3.4. Calculating Node Importance

To calculate the node importance in a network, we have to improve (2), where λ is the adjustment parameter to control the degree of adjacent nodes. When λ=1, node importance is totally decided by the importance of its adjacent nodes; when λ=0, all the node importance is (1-λ)(e/n), where e=[1,1,…,1]1×n, and there is no difference between all the nodes. Obviously, it is not reasonable because node importance should be related to the characteristics of adjacent nodes and itself. Only degree and betweenness are related to it due to the simplification of the contraction equations.Here, we use the normalized centrality to revise the parametere/n in PageRank algorithm and also insert the above matrixes into (5) to revise node importance IMnode:(5)IMnodeupdated=λ·T·IMnodecurrent+1-λ×Cn×1sumCn×1.Here, T is the transformation probability matrix as mentioned before, and λ is the influencing weight of the neighbor node importance on itself, and 1-λ is the influencing weight of the centrality Cn×1 of the network, which is calculated as described in Section 2.1. Periodically, the current node importance IMnodecurrent is updated by IMnodeupdated.


### 3.5. Con-Rank Node Importance Evaluation Algorithm

More detailed Con-rank node importance evaluation algorithm procedure is shown as Algorithm2. Lines 1–3 are the initialization of the algorithm, line 2 shows how to compute the value of contraction of vi, lines 4–7 are mean to update the topology without vi, lines 8–11 are the calculation of Sij, lines 12–15 are used to obtain the transmission matrix, and both line 16 and line 17 represent the computation of the central degree and the node importance, respectively.Algorithm 2:Con-rank node importance evaluation algorithm.
Input: Initial topology with total N node
Output: Every Nodes Importance
(1)N = RandomGenerate;
(2)H = RandomGenerate;
(3)   Compute the value of contractionsi according to formula (3);
(4)for  all  vi∈V  do
(5)  Generate new topology withoutvi;
(6)  Check the features of this topology;
(7)end
(8)   Compute the similaritySij between vi and vj as described in Section 3.3;
(9)for  all  vi∈V  do
(10)Sij=sisj,hij=10,hij=0
(11)end
(12) Compute matrix of transition probabilityT;
(13)for  all  vi∈V  do
(14)Tij=Sji∑j‍sji
(15)end
(16) ComputeCn×1 Central degree;
(17) Compute and outputIMnode according to formula (5);


## 3.1. Basis of Node Contraction

Here, we use node contraction algorithm proposed in [13] to calculate contraction value and is further used to compute the node importance. Because the node position and the degree are taken into account at the same time, the node importance in the network can be obtained.Definition 1.
Node contraction: there areki nodes, which are directly connected with node vi, and these nodes are all replaced by a new node vi′. One extreme example is that it becomes one-node network when the central node of a star network is contracted.Definition 2.
The cohesion degree ofG is that ∂[G]=1/(n·l)=1/(n·(∑i≠j∈Vlij)/n(n-1))=(n-1)/∑i≠j∈Vlij, where n≥2 and lij is the shortest distance from node i to node j, when n=1, ∂=1. Obviously 0<∂≤1, and ∂ gets the maximal value 1 when there is only one node in the network. So network cohesion degree is decided by connection ability of nodes in network, and one assumes that the average shortest distance between a couple of nodes is l. In addition, the number of nodes n can also influence network cohesion degree.Definition 3.
The contraction value of nodevi is si=1-∂[G]/∂[G∗vi], where G∗vi indicates the graph after contraction of node vi.Hence, according to Definitions1 and 2, we get (3)si=1-∂G∂G∗vi=1-1/n·lG1/n-ki·lG∗vi=n·lG-n-ni·lG∗vin·lG,where l is the same as that mentioned in Definition 2 and ki is the same as that mentioned in Definition 1.


## 3.2. Node Contraction Algorithm

Detailed node contraction procedure is listed in Algorithm1, in which the contraction value of node vi can be obtained.Algorithm 1:Node contraction algorithm.
Input:   Adjacent matrix H
Output: Node contraction value si
(1) Compute the direct distance matrix of all pairs of nodesD=[ddij];
(2) Compute cohesion degree∂[G] of the initial network according to Definition 2;
(3)for  all  vi∈V  do
(4)Compute the shortest distance matrix Di after node contraction based on vi, and Di=[lij]n×n;
(5)Compute cohesion degree ∂G∗vi according to Definition 2;
(6)Compute si according to Definition 3.
(7)endIn Algorithm1, we firstly have to get the direct distance matrix D=[ddij]n×n from the adjacent matrix H=[hij] of G: (4)ddij=0,ifi=j1,ifi≠j,hij=1∞,ifi≠j,hij=0.Secondly, we should update the shortest distancelpq′ between any node pair (vp,vq)∈V×V. Let I={vk∈V∣ddki≠∞} be the set of all the neighbor nodes and itself and the contraction of vi equal to ddst=0, s,t∈I. The corresponding update operations are listed as follows:(1)
vp≠vi and vq≠vi;
(i)
lpi+liq=lpq; that is, vi is in the shortest path between vp and vq; then lpq′=lpq-2;(ii)
lpi+liq=lpq+1; that is, vi is in the suboptimal path between vp and vq; then lpq′=lpq-1;(iii)
lpi+liq≥lpq+2; then lpq′=lpq;(2)
vp=vi or vq=vi; then lpq′=lpq-1;(3)
vi=vp=vq; then lpq′=lpq=0.Finally, all the nodes inI are replaced by a new node vi′ but the links between any pair of nodes remain, and we can get Li=[lpq′] by deleting the relative rows and column of vi in [lpq′]. When calculating Li, only n(n-1)/2 pairs of nodes need to be calculated because G is an undirected graph.


## 3.3. Computing Transformation Probability Matrix

S
i
j
=
s
i
/
s
j is the similarity of vi and vj, where si and sj are the contraction value of vi and vj, respectively, and can be calculated according to (3). Furthermore, we can compute the transformation probability matrix T, and Tij=Sji/∑jSji and T should be normalized further.


## 3.4. Calculating Node Importance

To calculate the node importance in a network, we have to improve (2), where λ is the adjustment parameter to control the degree of adjacent nodes. When λ=1, node importance is totally decided by the importance of its adjacent nodes; when λ=0, all the node importance is (1-λ)(e/n), where e=[1,1,…,1]1×n, and there is no difference between all the nodes. Obviously, it is not reasonable because node importance should be related to the characteristics of adjacent nodes and itself. Only degree and betweenness are related to it due to the simplification of the contraction equations.Here, we use the normalized centrality to revise the parametere/n in PageRank algorithm and also insert the above matrixes into (5) to revise node importance IMnode:(5)IMnodeupdated=λ·T·IMnodecurrent+1-λ×Cn×1sumCn×1.Here, T is the transformation probability matrix as mentioned before, and λ is the influencing weight of the neighbor node importance on itself, and 1-λ is the influencing weight of the centrality Cn×1 of the network, which is calculated as described in Section 2.1. Periodically, the current node importance IMnodecurrent is updated by IMnodeupdated.


## 3.5. Con-Rank Node Importance Evaluation Algorithm

More detailed Con-rank node importance evaluation algorithm procedure is shown as Algorithm2. Lines 1–3 are the initialization of the algorithm, line 2 shows how to compute the value of contraction of vi, lines 4–7 are mean to update the topology without vi, lines 8–11 are the calculation of Sij, lines 12–15 are used to obtain the transmission matrix, and both line 16 and line 17 represent the computation of the central degree and the node importance, respectively.Algorithm 2:Con-rank node importance evaluation algorithm.
Input: Initial topology with total N node
Output: Every Nodes Importance
(1)N = RandomGenerate;
(2)H = RandomGenerate;
(3)   Compute the value of contractionsi according to formula (3);
(4)for  all  vi∈V  do
(5)  Generate new topology withoutvi;
(6)  Check the features of this topology;
(7)end
(8)   Compute the similaritySij between vi and vj as described in Section 3.3;
(9)for  all  vi∈V  do
(10)Sij=sisj,hij=10,hij=0
(11)end
(12) Compute matrix of transition probabilityT;
(13)for  all  vi∈V  do
(14)Tij=Sji∑j‍sji
(15)end
(16) ComputeCn×1 Central degree;
(17) Compute and outputIMnode according to formula (5);


## 4. Con-Rank Topology Evolution for WSN

In the real world, the way for a node to connect other nodes is not global preferentialness as described in BA (Barabasi and Albert) scale-free network. In WSNs, nodes’ communication radius limits them to connect all the other nodes in networks. What is more, global preferentialness is impractical because it will cost vast energy of wireless sensor nodes which is also energy limited. So local optimum is needed. Finally, if the scheme only cares about nodes’ degree it may cause some nodes’ expiration quickly and shorten WSNs’ lifetime. Hence, this paper applies the Con-rank algorithm to form the new preferential attachment rules and to select the candidate node connecting to the newest node. The topology evolution process is shown as follows.


### 4.1. Topology Evolution Process

(i)
Initialization. Initialize the network with a small scale topology which consists of m0 nodes, e edges, and a sink node.
(ii)
Growth and Preferential Attachment. Let a new node join the network with m edges from the node to previous ones. And the probability of the previous node i being chosen is (6)∏i=IMnodei∑jIMnodej·Pdij≤dmax⁡,
whereIMnode(i) is the value calculated by Con-rank equation.
(iii)
Use the Con-rank equation to update theIMnode(i) and cycle until the total number of nodes reaches N.


### 4.2. Dynamic Analysis of Topology Evolution

Theory 1. Con-rank evolution topology agrees with power-law distribution.Proof.
According to mean-field theory [6], we assume that ki is continuous, and the probability of connecting to a node ∏i‍ can be interpreted as a continuous rate of change of k,(7)∂ki∂t≈m∏i=mIMnodei∑jIMnodej·Pdij≤dmax,where P{dij≤dmax⁡}=πd2/S and S is the largest communication area.
According to [13], si=θ1ki+θ2Bi, where θ1 and θ2 are fixed parameter.
AndIMnode=α(si)+βCi; then (8)IMnode=α′ki+β′θ2Bi+Ci,where α′ and β′ are constants.
Substitute (8) into formula (7); we get (9)∂ki∂t=mα′ki+β′θ2Bi+Ci∑jα′ki+β′θ2Bi+Ci·πd2S.
Because every edge contributes 2 degrees, then∑jkj=2mt. And let θ2B+C be the average of θ2Bi+Ci; then ∑jθ2Bi+Ci=θ2B+Ct. So (10)∂ki∂t=α′ki+β′θ2Bi+Ci2α′t+β′m-1θ2B+Ct·πd2S.
Assume that when nodei enters into the network at ti every new node has initial degree ki(ti)=m. Meanwhile, let α′′=α′·πd2/S=αθ1·πd2/S and β′′=β·πd2/S; we get the answer which fits this initial condition:(11)kit=-δi+m+δitti1/γ,where γ=(2α′′+β′′m-1θ2B+C)/α′′ and δi=(β′′/α′′)(θ2Bi+Ci).
The probability of the degree of the node which enters atti is less than k at t; that is, (12)pkit≤k=pti≥m+δiγ·tk+δiγ.
Assume that the new node is added to the network regularly, and random variableti agrees with the uniform distribution in (0,t), and then the probability is (13)pti=1m0+t.
Substitute (13) into formula (12); we get(14)pkit≤k=1-pti<m+δiγ·tk+δiγ=1-m+δiγ·tk+δiγm0+t.
Then the degree distribution of Con-rank topology evolution is(15)pk=∂kit≤k∂k=γm+δiγk+δi-γ+1tm0+t.
And then(16)limt→∞⁡pk=∂kit≤k∂k=γm+δiγk+δi-γ+1.
Take logarithm of both sides of formula (16): (17)ln⁡⁡pk=ln⁡⁡γ+γln⁡⁡m+δi-γ+1k+δi.
From the above formulas, the degree distribution of nodei is independent of time. When k→∞, we get (18)ln⁡⁡pkln⁡⁡k≈-γ+1=3+β′′m-1θ2B+Cα′′.
Hence the degree distributions of all nodes nearly agree with power-law distribution with an exponent-(3+β′′m-1〈θ2B+C〉/α′′).


## 4.1. Topology Evolution Process

(i)
Initialization. Initialize the network with a small scale topology which consists of m0 nodes, e edges, and a sink node.
(ii)
Growth and Preferential Attachment. Let a new node join the network with m edges from the node to previous ones. And the probability of the previous node i being chosen is (6)∏i=IMnodei∑jIMnodej·Pdij≤dmax⁡,
whereIMnode(i) is the value calculated by Con-rank equation.
(iii)
Use the Con-rank equation to update theIMnode(i) and cycle until the total number of nodes reaches N.


## 4.2. Dynamic Analysis of Topology Evolution

Theory 1. Con-rank evolution topology agrees with power-law distribution.Proof.
According to mean-field theory [6], we assume that ki is continuous, and the probability of connecting to a node ∏i‍ can be interpreted as a continuous rate of change of k,(7)∂ki∂t≈m∏i=mIMnodei∑jIMnodej·Pdij≤dmax,where P{dij≤dmax⁡}=πd2/S and S is the largest communication area.
According to [13], si=θ1ki+θ2Bi, where θ1 and θ2 are fixed parameter.
AndIMnode=α(si)+βCi; then (8)IMnode=α′ki+β′θ2Bi+Ci,where α′ and β′ are constants.
Substitute (8) into formula (7); we get (9)∂ki∂t=mα′ki+β′θ2Bi+Ci∑jα′ki+β′θ2Bi+Ci·πd2S.
Because every edge contributes 2 degrees, then∑jkj=2mt. And let θ2B+C be the average of θ2Bi+Ci; then ∑jθ2Bi+Ci=θ2B+Ct. So (10)∂ki∂t=α′ki+β′θ2Bi+Ci2α′t+β′m-1θ2B+Ct·πd2S.
Assume that when nodei enters into the network at ti every new node has initial degree ki(ti)=m. Meanwhile, let α′′=α′·πd2/S=αθ1·πd2/S and β′′=β·πd2/S; we get the answer which fits this initial condition:(11)kit=-δi+m+δitti1/γ,where γ=(2α′′+β′′m-1θ2B+C)/α′′ and δi=(β′′/α′′)(θ2Bi+Ci).
The probability of the degree of the node which enters atti is less than k at t; that is, (12)pkit≤k=pti≥m+δiγ·tk+δiγ.
Assume that the new node is added to the network regularly, and random variableti agrees with the uniform distribution in (0,t), and then the probability is (13)pti=1m0+t.
Substitute (13) into formula (12); we get(14)pkit≤k=1-pti<m+δiγ·tk+δiγ=1-m+δiγ·tk+δiγm0+t.
Then the degree distribution of Con-rank topology evolution is(15)pk=∂kit≤k∂k=γm+δiγk+δi-γ+1tm0+t.
And then(16)limt→∞⁡pk=∂kit≤k∂k=γm+δiγk+δi-γ+1.
Take logarithm of both sides of formula (16): (17)ln⁡⁡pk=ln⁡⁡γ+γln⁡⁡m+δi-γ+1k+δi.
From the above formulas, the degree distribution of nodei is independent of time. When k→∞, we get (18)ln⁡⁡pkln⁡⁡k≈-γ+1=3+β′′m-1θ2B+Cα′′.
Hence the degree distributions of all nodes nearly agree with power-law distribution with an exponent-(3+β′′m-1〈θ2B+C〉/α′′).


## 5. Simulation Results

According to Con-rank topology evolution model, we use MATLAB to simulate the topology process and get several pieces of related data to perform the analysis. We will compare several characteristics in both Con-rank model and BA model, such as degree distribution, average path length, and clustering coefficient.


### 5.1. Degree Distribution

Degree distributionp(k) is the basic topology characteristics in complex network. Here, we will analyze the distribution probability upon the different node degree by the numerical simulation, and we set the total number of nodes N=500, the initial nodes m0=3, the number of inserting nodes m=1, and the inserting link length be 1, which is with probability λ=0.5. The mean of the data is based on 20 repeated experiments and relationships of node degree and distribution probability are showed in Figure 1, where the abscissa denotes the node degrees and the ordinate refers to the degree distribution probability.Figure 1
Degree distribution of Con-rank evolution.From Figure1, in which nodes show empirical results and small circles represent theoretical results, we find degree distribution allows the power laws and the two results fit each other well. In addition, when random variables β′′, θ2, and α′′ make β′′〈θ2B+C〉/mα′′=0 according to the theoretical analysis, this model becomes the classic BA model.


### 5.2. Clustering Coefficient

Clustering coefficient, which comes from the proportion of a man’s friends who are also friends with each other, is used to show the nodes connection condition. And it is also a key parameter to measure the density of a network.Letm0=3 and m=1 and calculate the clustering coefficient in the two models. The mean of the data is based on 20 repeated experiments and the clustering coefficient comparison are shown in Figure 2, where the abscissa denotes the numbers of nodes from 100 to 500 and the ordinate refers to the clustering coefficient.Figure 2
Clustering coefficient comparison.From Figure2, the clustering coefficient by Con-rank is larger than that by BA model in the same size; that is, it is more likely to see nodes gathering in a small district in Con-rank model.


### 5.3. Average Path Length

Communication delay is one of the vital factors influencing the functions of networks, and path and diameter are the main parameters, which are not used to predict the whole networks. So average path length is introduced to reflect the whole networks’ characteristics. Set these parameters as above and get the mean of the data from 20 repeated experiments and relationships are showed in Figure3, where the abscissa denotes the numbers of nodes from 100 to 500 and the ordinate refers to the average path length.Figure 3
Average path length comparison.From Figure3, the average path length in Con-rank is shorter than that in BA model, which fits the small-world model better.In addition, the Con-rank evolution model has shorter average path length and larger clustering coefficient and can construct a robust topology to defend both random and targeted attacks.


## 5.1. Degree Distribution

Degree distributionp(k) is the basic topology characteristics in complex network. Here, we will analyze the distribution probability upon the different node degree by the numerical simulation, and we set the total number of nodes N=500, the initial nodes m0=3, the number of inserting nodes m=1, and the inserting link length be 1, which is with probability λ=0.5. The mean of the data is based on 20 repeated experiments and relationships of node degree and distribution probability are showed in Figure 1, where the abscissa denotes the node degrees and the ordinate refers to the degree distribution probability.Figure 1
Degree distribution of Con-rank evolution.From Figure1, in which nodes show empirical results and small circles represent theoretical results, we find degree distribution allows the power laws and the two results fit each other well. In addition, when random variables β′′, θ2, and α′′ make β′′〈θ2B+C〉/mα′′=0 according to the theoretical analysis, this model becomes the classic BA model.


## 5.2. Clustering Coefficient

Clustering coefficient, which comes from the proportion of a man’s friends who are also friends with each other, is used to show the nodes connection condition. And it is also a key parameter to measure the density of a network.Letm0=3 and m=1 and calculate the clustering coefficient in the two models. The mean of the data is based on 20 repeated experiments and the clustering coefficient comparison are shown in Figure 2, where the abscissa denotes the numbers of nodes from 100 to 500 and the ordinate refers to the clustering coefficient.Figure 2
Clustering coefficient comparison.From Figure2, the clustering coefficient by Con-rank is larger than that by BA model in the same size; that is, it is more likely to see nodes gathering in a small district in Con-rank model.


## 5.3. Average Path Length

Communication delay is one of the vital factors influencing the functions of networks, and path and diameter are the main parameters, which are not used to predict the whole networks. So average path length is introduced to reflect the whole networks’ characteristics. Set these parameters as above and get the mean of the data from 20 repeated experiments and relationships are showed in Figure3, where the abscissa denotes the numbers of nodes from 100 to 500 and the ordinate refers to the average path length.Figure 3
Average path length comparison.From Figure3, the average path length in Con-rank is shorter than that in BA model, which fits the small-world model better.In addition, the Con-rank evolution model has shorter average path length and larger clustering coefficient and can construct a robust topology to defend both random and targeted attacks.


## 6. Conclusions

In this paper, we build a new node importance evaluation model, Con-rank evaluation model, which is based on PageRank and node contraction algorithms. It evaluates node in multiple angles and fits the real network better. In addition, limited energy and robustness are the main problems in WSNs; thus it is a key to enhance lifetime and keep scale-free characteristics for a scale-free network. So this paper proposes Con-rank evolution model to build a superior scale-free network and gives a dynamic analysis of topology evolution. Finally, a simulation is performed to evaluate the model characteristics and network performances. Simulation results agree with theoretical analysis and show that Con-rank evolution model has shorter average path length and bigger clustering coefficient.



---

*Source: 165136-2015-09-27.xml*