# Energy-Aware Topology Evolution Model with Link and Node

Authors: Xiaojuan Luo; Huiqun Yu; Xiang Wang
Journal: Mathematical Problems in Engineering
 (2012)

---

## Abstract

Based on the complex network theory, a new topological evolving model is
proposed. 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. Theoretical
analysis and numerical simulation are conducted to explore the
topology characteristics and network performance with different node
energy distribution. We find that node energy distribution has the
weak effect on the degree distributionP(k) that evolves into the scale-free state, nodes with more
energy carry more connections, and degree correlation is nontrivial
disassortative. Moreover, the results show that, when nodes energy is
more heterogeneous, the network is better clustered and enjoys higher
performance in terms of the network efficiency and the average path
length for transmitting data.


---

## Body

## 1. Introduction

Recently, complex networks have attracted considerable intention to investigate various real-world dynamic networks, such as scientific collaboration, the Internet, worldwide web, social networks, biological networks, transportation networks, e-mail networks, software engineering, and ad hoc networks; see [1–9] and the references therein. In the original theoretical description of these findings, the Watts-Strogatz (WS) model [10] provided a simple way to generate networks with the “small-world” properties. Barabási and Albert [11] proposed a “scale-free” network with a power-law degree distribution. Further studies show that real networked systems may undergo the more complex evolution process governed by multiple mechanisms on which the occurrence of network structures depends [12–15]. Therefore, to get a better understanding of the real-world system, it is necessary to describe such evolution processes of complex network in more detailed and realistic manner.The motivation for considering dynamic networks comes, in part, from the recent interest in designing wireless sensor networks as a prime example. Sensor networks have recently received increasing interests due to their extensive application in areas such as information collection, environmental monitoring, industrial automation, health tracking, and military surveillance [16, 17]. Consequently, many critical techniques in sensor network have gained much research efforts [18–22]. The motivations of this work is to continue such efforts aimed at discovering new mechanism to construct optimal network structures and that might be useful in designing engineered senor networks.Well-known examples of such dynamical network models are proposed including preferential attachment and its variants [11, 23, 24]. Very recently, Zhu et al. [25] have proposed two scale-free networks-based models for wireless sensor networks, named energy-aware evolution model (EAEM) and energy-balanced evolution model (EBEM) which can organize the networks in an energy-efficient way. Chen et al. [26] have proposed a topology control of wireless sensor networks under an average degree constraint. Actually, the above evolving models have considered energy efficiency of WSNs using by energy-aware mechanism. These mechanisms, however, model the dynamics WSN as a monotonously growing network, where the effect of node deletion is not considered to be significant. Sensor networks experience significant rates of links and nodes deletion for several kinds of cases as follows and beyond. Nodes join and depart from sensor networks in a random and rapid manner for artificial mobility. The links and nodes are probably removed for many factors such as environment deteriorated, hostile attack because the sensor nodes are usually deployed over some inaccessible and dangerous geographical area. Usually the energy of sensor node is limited and nonrecharged and would be exhausted after working for a period of time. Hence, developing a network dynamic model for the real-world sensor networks with a significant deletion component is necessary.Several recently proposed models have addressed the link and node deletion process for dynamical sensor network. Kong and Roychowdhury [27] proposed an ad hoc network with node addition and removal, focusing on the compensatory process for node removal to preserve true scale-free state. Sarshar and Roychowdhury [28] investigated stable ad hoc network where nodes deletion is dominated by preferential survival mechanism. A local-world heterogeneous model of wireless sensor networks with node and link diversity was proposed in [29]. Unfortunately, those works have not considered the node energy problem in the network. Energy efficiency is a critical factor for prolonging the life of the network system. If the topology is constructed based on the node energy, then the traffic load is properly adjusted, that is, nodes with more energy carry more connections and the node with less energy will carry few connections. The energy consumption is balanced in the whole network, and the network lifetime will be effectively extended.Motivated by the above analysis, in this paper, we aim to investigate the topological evolving model for wireless sensor network, which is combined energy-aware mechanism with both addition and removal of link and node based on complex network theory. To the best of the authors’ knowledge, the proposed mechanism has not yet been addressed for WSNs. The main contributions of this paper are summarized as follows. (1) a new evolution model is proposed to describe dynamical sensor network. (2) a combination of two important mechanisms of energy preferential attachment for link and node addition and energy antipreferential attachment for link and deletion contributes to investigating the complexity of WSNs. (3) Degree distributionP(k) is solved by utilizing mean-field analysis and shows how the network evolves into the scale-free state. Numerical simulations of several critical topology characteristics are used to demonstrate the effectiveness of the proposed model in this paper.The rest of this paper is organized as follows. In Section2, we present our new energy-aware topology evolving model for wireless sensor networks. In Section 3, we give the numerical analysis and simulations experiments discussion about the network characteristics under the effect of different node energy distribution. Its effectiveness is analytically investigated by its topology properties, such as degree distribution, node degree, and the average degree of neighboring node, the average clustering coefficient, the average path length, and the network efficiency. The results are validated through numerical calculations and simulations. Finally in Section 4, we conclude the investigation and point out the further research direction.


## 2. The Proposed Model for WSNs

In this section, we present the following model to capture the particular features of such WSNs evolving networks. In the initial state, the network has a small numbern0 of connected nodes and small number e0 of edges. Then, the iterative algorithm during the evolving process is outlined as follows.(1) Preferential Attachment
At each time step, a new node is added to the system. Andm (0<m≤n0) new links from the new node are connected to m existing nodes. We assume that the preferential probability Π(ki) of a new node will be connected to node i depending on the connectivity ki and energy (Ei) of that node. In this paper, we use the definition of the function f(Ei) to present the relationship between the energy of a node and its ability to be linked just as in [25]. Then
(2.1)Π(ki)=f(Ei)ki∑jf(Ej)kj.
In real wireless sensor network, the node which has more connetivities will carry more traffic load and consume its energy more quickly. For the balance the energy consumption, we assume the more energy a node has, the strong ability it will have of being connected to the new coming nodes. Therefore,f(Ei) must be an increasing function here, and the form may be as βEi, βEi2 and so on. Here β is the coefficient. In this paper, we just set f(Ei)=Ei, where β=1. And the form of Π(ki) is expressed as
(2.2)Π(ki)=Eiki∑jEjkj.(2) Links Deletion
At each time step, with probabilityp (0≤p<1), m*p old links are removed. So the parameter p denotes the deletion rate, which is defined as the rate of links removed divided by the rate of links addition. We first select a node i as an end of a deleted link with the antipreferential probability as (2.2). The less energy the node has, the more probability it will have for being deleted:
(2.3)Π*(ki)=(kiEi)-1∑i(kiEi)-1.
Then nodej is then chosen from the linked neighborhood of node i (denoted by Oi) with probability Ki-1Π*(kj), where Ki=∑j∈OiΠ*(kj). Then the link connecting nodes i and j is removed; this process is repeated m*p times. Once an isolated node appears, it should be removed from the network to maintain the connectivity of networks. The antipreferential removal mechanism is more reasonable for deleting links that are parallel with the preferential connection. It is consistent with the real wireless sensor networks environment. The wireless links that have not been active may be removed from the network when the energy of the connecting nodes falls down to a certain level. The particular antipreferential removal phenomenon is also reasonable for many real networks. For example, users’ e-mail networks can be constructed by considering user address books as nodes and addresses in the address books as links. Some old addresses that have become inactive below the threshold may be deleted in the evolving e-mail network [8]. Furthermore, in the evolving words network, there will be link and node removals over time because some old expressions and sentences are no longer used and some words may become obsolete [12].


## 3. Network Analysis

Topological characterization is of great importance for network structure in reality. To have a better understanding of the complex dynamics in the considered model and of the influence ofρ(E), in this section we give theoretical analysis and numerical simulation of these statistical properties parameters—the degree distribution P(k), node degree (kE), the average nearest-neighbor connectivity (knn(k)), the average clustering coefficient (C), the average path length (L), and the network efficiency (E).


### 3.1. Degree Distribution

The degree distributionP(k), which indicates the probability that a randomly selected node has k connections, is  very important statistical character of large-scale complex network. In fact, P(k) has been suggested to be used as the first criterion to classify real-world networks. Now we adopt the mean field theory [30] to give a qualitative analysis of P(k) for our energy-aware evolving model with link and node deletions.By the mean-field theory, letki(t) be the degree of the ith node at time t, then in the limit of large t, the increasing rate of ki(t) satisfies the following dynamical equation:(3.1)∂ki∂t=mΠ(ki)-mp[Π*(ki)+∑j∈linked(i)Π*(kj)Ki-1Π*(ki)].It is easy to know that the first term in (3.1) accounts for the increasing number of links of the ith node by the preferential attachment due to the newly added node. The second term in (3.1) explains the losing of links by antipreferential attachment during the evolving process.From the mean-field sense, we have(3.2)∑jEjkj=N(t)*E¯*〈k(t)〉,
where E¯ is the expected value of the node energy in the whole network; N(t) is the number of the nodes at time step t; 〈k(t)〉 is the average degree of the network at time t. For large t, N(t)=n0+t≈t; 〈k(t)〉=(2m(1-p)t+e0)/(m0+t)≈2m(1-p) with e0 being the number of edges that were initially linked to n0 nodes. Moreover we can have ∑j∈O(i)Ki-1Π*(ki)≈1. Then, at time step t, Π*(ki)≈1/N(t)≈1/t, which indicates that link deletion with the antipreferential probability is equivalent to deleting links with equal probability by mean-field sense. This phenomenon is also observed in [12].Supposing that sensor networks which undergo a large number of time stepst have sufficiently large scale, we obtain  (3.3)∂ki∂t≈mEiki2m(1-p)E¯t-2mpt.It is obvious that, at every time stept, 0≤p<1. Since p=1, the network cannot grow. We then consider two cases in the above proposed evolving network model: p=0 and 0<p<1, which are further discussed below.Case A (p=0).
In this case, there are only link and node additions without link and node deletions in the evolving process as in [25]. It is usually fit for topology discovery state of WSNs in which the all nodes have enough power in the ideal environment. So ki(t) satisfies
(3.4)∂ki∂t=mEikiNE¯〈k(t)〉=Eiki2(n0+t)E¯≈Eiki2tE¯.
With the initial conditionki(ti)=m, then we can get
(3.5)ki(t)=mEi2E¯(tti)1/2.
The probability that a node has a connectivity which satisfyki(t)<k is
(3.6)P(ki(t)<k)=P(ti>12(mEi2E¯)2tk2).
Assuming that we add the node to the network at equal time intervals in evolving process for WSNs, the probability density at the timeti is P(ti)=1/(n0+t). Therefore, we get
(3.7)P(ki(t)<k)=1-12(mEi2E¯)2tk21n0+t.
The probability density function of the degree of a node with energyE is
(3.8)P(kE)=∂P(ki(t)<k)∂k=2n0+t(mE2E¯)2tk3.
The overall probability density function is(3.9)P(k)=∫Emin⁡Emax⁡ρ(E)P(kE)dE=∫Emin⁡Emax⁡ρ(E)12(n0+t)(mEE¯)2tk3dE=∫Emin⁡Emax⁡12ρ(E)(mEE¯)21k3dE,t⟶∞,
where ρ(E) is the probability density distribution of node energy E in the whole network; Emin and Emax are the bounds of node energy values. Obviously, p(k)∝λk-3, where λ=∫EminEmax(1/2)ρ(E)(mE/E¯)2dE. The degree distribution follows the same power law as the Barabási-Albert scale-free model [11].Case B (0<p<1).
In this case, links and nodes in the evolving network model are not monotonously growing. Instead, links and nodes can be added in some occasion and removed in other case. We rewrite (3.3) as follows:
(3.10)∂ki∂t=mEiki2m(1-p)E¯t-2mpt.
With the initial condition that nodei at its introduction has ki(ti)=m, one can get
(3.11)ki(t)=B(tti)β-B+mforlarget,
where the dynamic exponent is
(3.12)β=β(m,p)=mEi[2m(1-p)+1]E¯
and the coefficient is
(3.13)B=B(m,p)=m-m-2mp[2m(1-p)+1]mE¯Ei.
We can get from (3.11) that
(3.14)P(ki(t)<k)=P(ti>(BB-m+k)1/βt)fork>m.
With the same about the probability density at the timeti, P(ti)=1/(n0+t). Hence,
(3.15)P(ki(t)<k)=1-(BB-m+k)1/βtn0+t.
The probability density function of the degree of a node with energyE is
(3.16)P(kE)=∂P(ki(t)<k)∂k=tn0+t1βB1/β(k+B-m)-(1+1/β).
To obtain the overall probability density function(3.17)P(k)=∫Emin⁡Emax⁡ρ(E)P(kE)dE=∫Emin⁡Emax⁡ρ(E)tn0+t1βB1/β(k+B-m)-(1+1/β)dE,
where ρ(E), Emin, and Emax have the same definition as in (3.9). We compute numerical results and compare them with simulation as follows.In this paper, we consider three kinds of node energy distributionρ(E) in the whole network within the interval [0J,1J]: (1) the same node energy with value 0.5J with σ=0; (2) uniform distribution (U[0J,1J]) with σ=1/12; (3) exponential distribution (exp(-E)) with σ=1, where σ is the standard deviation used to indicate the node energy heterogeneity. The nodes energy in the network becomes more and more heterogeneous as σ increases. So, the node energy with exponential distribution is the most heterogeneous among the three cases, while the node energy is homogeneous with σ=0 for the first case.In Figure1, we make the simulations for m=4 and m=1, where p=0. We can find that the degree distributions P(k) are power law as B-A model. Moreover, it is easy to understand that the network makes higher connectivity as m increases. We also can see that the network degree distribution curves obtained by the mathematic method and by simulation match very well.Figure 1
The degree distributionP(k) obtained by simulations as hollow symbol for m=4; face color marked symbol for m=1, with three kinds of ρ(E), by the mean-field method as dashed line, where p=0, t=2000.In Figures2, 3(a) and 3(b), we, respectively, give the simulations for p=0.5,p=0.75, and p=0.25, where m=4, t=2000. We observe that the results of P(k) display a horse-head-like curve, with its middle section showing the expected scale-free state whatever the value of p is. We can see that the network degree distribution curves obtained by the mean-field method and by simulation match very well for degree larger than m. The figures also show that the mean-field solution cannot provide probabilities for degrees smaller than m. The overall horse-head-like distribution curve has also been observed in [12] by Markov process. Thus, from Figures 1, 2, and 3, there is little distinction among the plots for three kinds of nodes energy distribution. So we think the different nodes energy distribution in the network has the weakest affect on the degree distribution.Figure 2
The degree distributionP(k) obtained by simulations with three kinds of ρ(E): same (0.5J), U[0,1], exp(-E) and by fitting line as dashed line, by the mean-field method as solid green line, where m=4, p=0.5, t=2000.The degree distributionP(k) obtained by simulations for three kinds of node energy distribution ρ(E) and by fitting line as dashed line; (a) p=0.25, (b) p=0.75; where m=4, t=2000.
(a)(b)


### 3.2. Connectivity Correlation

To clearly understand the influence ofρ(E) on the network connectivity and uncover the internal complexity of the topological structure, it is worth investigating the connectivity correlation through kE (the average degree of node with energy E) and knn(k) (the average degree of neighboring nodes of a given node with degree k). We find from Figure 4 that the node which has more energy has a larger degree. The node degree is linearly increased with node energy when ρ(E) is uniform distribution. But for the exponential distribution, there is an inward bend at the middle of the data curve that most high energy nodes carry much more links and a few of them keep relatively less links. It is because we can only perform a finite number of computation steps, and then possibly some nodes with high energy newly come into the network. There are a few hubs, that have much more links than the others nodes, emerging in the evolving process for the energy exponential distribution case. Thus the connectivity becomes more inhomogeneous when nodes energy is more heterogeneous.Figure 4
The relation between node degree and node energy obtained by simulations for two kinds of node energy distributionρ(E): U[0,1], exp(-E), where m=4, p=0.5.Connectivity correlation is also quantified by reporting the numerical value of the slope ofknn(k) as a function of K. We compute knn(k) which is defined as in [31]:(3.18)knn(k)=1Nk∑i∈Ωk(1k∑j∈Oikj),
where Ωk is the set of nodes with degree K of the amount Nk in the evolving WSNs. Oi is the set of linked neighbors of node i. In Figure 5, it is found that knn(k) is independent of K for nodes with large degree, that is, nodes with large k show no obvious biases in their connections. But there is a short disassortative region when k is relatively small, that is, nodes with low degree are more likely linked with the highly connected ones. Such phenomenon can be explained by the effect of network growth with energy preferential attachment and elements removals with antipreferential mechanism.Figure 5
The average degree of neighboring nodeknn(k) obtained by simulations for three kinds of node energy distribution ρ(E), where m=4, p=0.5.


### 3.3. Clustering Coefficient

We investigate the effect of node energy distribution on network’s cluster coefficient, which quantifies the extent to which nodes adjacent to a given node are linked [15, 31]. Let Ei denote the number of edges among the neighbor nodes of a selected node i with degree ki in the network; Ci is local clustering coefficient of node i. Then the clustering coefficient of the whole network is the average of all individual Ci. It is defined as follows: (3.19)C=1N∑iCi=1N∑iEiki(ki-1)/2.In Figure6, we give the clustering coefficient (C) changing by network size with three kinds of node energy distribution. C keeps very small value of 0.005 when node energy is same in the network. But when ρ(E) is exponential distribution, C keeps large value with the average value 0.185. The result indicates that nodes energy heterogeneity makes the network more clustering.Figure 6
The clustering coefficient obtained by simulations for three kinds of node energy distributionρ(E), where m=4, p=0.5.


### 3.4. Average Shortest Path Length and Network Efficiency

In WSN, the sensor nodes forward the data by multihops. The average path lengthL is defined to be the average length of the shortest paths between any two nodes in the network that is written as in (3.20). Usually we use it to measure the average hops among the nodes for data processing. Simultaneously we use the network efficiency E to measure how efficiently the information is exchanged over the network. Let dij denote the length of the shortest path between node i and node j. The efficiency between node i and j is assumed to be inversely proportional to the shortest distance: eij=1/dij. With this definition, when there is no path between i and j, dij=∞. The global efficiency of the network is defined as the average of the efficiencies over all couples of nodes. Its calculation can be defined as (3.21):(3.20)L=1N(N-1)∑i≠jdij,(3.21)E=1N(N-1)∑i≠j1dij.SinceL and E characterize the ability of two nodes to communicate with each other, the smaller L and the larger E mean fewer hops and less energy consumption for data processing. In Figures 7 and 8, we plot the average shortest path length (L) and network efficiency (C) with evolving time step t, which denoted network size, for three kinds of node energy distribution. We observe that L increases, and E decreases with the network size increasing. We also find, by the same evolving time step t, that the network obtains the smallest L and the largest E when ρ(E) is exponential distribution among the three kinds of ρ(E). Conversely, L is the largest and E is the smallest when node energy is same in the network for the same network size. The results verify that nodes in energy inhomogeneous networks are more efficient to communicate with others.Figure 7
The average shortest path length obtained by simulations for three kinds of node energy distributionρ(E), where m=4, p=0.5.Figure 8
The network efficiency obtained by simulations for three kinds of node energy distributionρ(E) where m=4, p=0.5.


## 3.1. Degree Distribution

The degree distributionP(k), which indicates the probability that a randomly selected node has k connections, is  very important statistical character of large-scale complex network. In fact, P(k) has been suggested to be used as the first criterion to classify real-world networks. Now we adopt the mean field theory [30] to give a qualitative analysis of P(k) for our energy-aware evolving model with link and node deletions.By the mean-field theory, letki(t) be the degree of the ith node at time t, then in the limit of large t, the increasing rate of ki(t) satisfies the following dynamical equation:(3.1)∂ki∂t=mΠ(ki)-mp[Π*(ki)+∑j∈linked(i)Π*(kj)Ki-1Π*(ki)].It is easy to know that the first term in (3.1) accounts for the increasing number of links of the ith node by the preferential attachment due to the newly added node. The second term in (3.1) explains the losing of links by antipreferential attachment during the evolving process.From the mean-field sense, we have(3.2)∑jEjkj=N(t)*E¯*〈k(t)〉,
where E¯ is the expected value of the node energy in the whole network; N(t) is the number of the nodes at time step t; 〈k(t)〉 is the average degree of the network at time t. For large t, N(t)=n0+t≈t; 〈k(t)〉=(2m(1-p)t+e0)/(m0+t)≈2m(1-p) with e0 being the number of edges that were initially linked to n0 nodes. Moreover we can have ∑j∈O(i)Ki-1Π*(ki)≈1. Then, at time step t, Π*(ki)≈1/N(t)≈1/t, which indicates that link deletion with the antipreferential probability is equivalent to deleting links with equal probability by mean-field sense. This phenomenon is also observed in [12].Supposing that sensor networks which undergo a large number of time stepst have sufficiently large scale, we obtain  (3.3)∂ki∂t≈mEiki2m(1-p)E¯t-2mpt.It is obvious that, at every time stept, 0≤p<1. Since p=1, the network cannot grow. We then consider two cases in the above proposed evolving network model: p=0 and 0<p<1, which are further discussed below.Case A (p=0).
In this case, there are only link and node additions without link and node deletions in the evolving process as in [25]. It is usually fit for topology discovery state of WSNs in which the all nodes have enough power in the ideal environment. So ki(t) satisfies
(3.4)∂ki∂t=mEikiNE¯〈k(t)〉=Eiki2(n0+t)E¯≈Eiki2tE¯.
With the initial conditionki(ti)=m, then we can get
(3.5)ki(t)=mEi2E¯(tti)1/2.
The probability that a node has a connectivity which satisfyki(t)<k is
(3.6)P(ki(t)<k)=P(ti>12(mEi2E¯)2tk2).
Assuming that we add the node to the network at equal time intervals in evolving process for WSNs, the probability density at the timeti is P(ti)=1/(n0+t). Therefore, we get
(3.7)P(ki(t)<k)=1-12(mEi2E¯)2tk21n0+t.
The probability density function of the degree of a node with energyE is
(3.8)P(kE)=∂P(ki(t)<k)∂k=2n0+t(mE2E¯)2tk3.
The overall probability density function is(3.9)P(k)=∫Emin⁡Emax⁡ρ(E)P(kE)dE=∫Emin⁡Emax⁡ρ(E)12(n0+t)(mEE¯)2tk3dE=∫Emin⁡Emax⁡12ρ(E)(mEE¯)21k3dE,t⟶∞,
where ρ(E) is the probability density distribution of node energy E in the whole network; Emin and Emax are the bounds of node energy values. Obviously, p(k)∝λk-3, where λ=∫EminEmax(1/2)ρ(E)(mE/E¯)2dE. The degree distribution follows the same power law as the Barabási-Albert scale-free model [11].Case B (0<p<1).
In this case, links and nodes in the evolving network model are not monotonously growing. Instead, links and nodes can be added in some occasion and removed in other case. We rewrite (3.3) as follows:
(3.10)∂ki∂t=mEiki2m(1-p)E¯t-2mpt.
With the initial condition that nodei at its introduction has ki(ti)=m, one can get
(3.11)ki(t)=B(tti)β-B+mforlarget,
where the dynamic exponent is
(3.12)β=β(m,p)=mEi[2m(1-p)+1]E¯
and the coefficient is
(3.13)B=B(m,p)=m-m-2mp[2m(1-p)+1]mE¯Ei.
We can get from (3.11) that
(3.14)P(ki(t)<k)=P(ti>(BB-m+k)1/βt)fork>m.
With the same about the probability density at the timeti, P(ti)=1/(n0+t). Hence,
(3.15)P(ki(t)<k)=1-(BB-m+k)1/βtn0+t.
The probability density function of the degree of a node with energyE is
(3.16)P(kE)=∂P(ki(t)<k)∂k=tn0+t1βB1/β(k+B-m)-(1+1/β).
To obtain the overall probability density function(3.17)P(k)=∫Emin⁡Emax⁡ρ(E)P(kE)dE=∫Emin⁡Emax⁡ρ(E)tn0+t1βB1/β(k+B-m)-(1+1/β)dE,
where ρ(E), Emin, and Emax have the same definition as in (3.9). We compute numerical results and compare them with simulation as follows.In this paper, we consider three kinds of node energy distributionρ(E) in the whole network within the interval [0J,1J]: (1) the same node energy with value 0.5J with σ=0; (2) uniform distribution (U[0J,1J]) with σ=1/12; (3) exponential distribution (exp(-E)) with σ=1, where σ is the standard deviation used to indicate the node energy heterogeneity. The nodes energy in the network becomes more and more heterogeneous as σ increases. So, the node energy with exponential distribution is the most heterogeneous among the three cases, while the node energy is homogeneous with σ=0 for the first case.In Figure1, we make the simulations for m=4 and m=1, where p=0. We can find that the degree distributions P(k) are power law as B-A model. Moreover, it is easy to understand that the network makes higher connectivity as m increases. We also can see that the network degree distribution curves obtained by the mathematic method and by simulation match very well.Figure 1
The degree distributionP(k) obtained by simulations as hollow symbol for m=4; face color marked symbol for m=1, with three kinds of ρ(E), by the mean-field method as dashed line, where p=0, t=2000.In Figures2, 3(a) and 3(b), we, respectively, give the simulations for p=0.5,p=0.75, and p=0.25, where m=4, t=2000. We observe that the results of P(k) display a horse-head-like curve, with its middle section showing the expected scale-free state whatever the value of p is. We can see that the network degree distribution curves obtained by the mean-field method and by simulation match very well for degree larger than m. The figures also show that the mean-field solution cannot provide probabilities for degrees smaller than m. The overall horse-head-like distribution curve has also been observed in [12] by Markov process. Thus, from Figures 1, 2, and 3, there is little distinction among the plots for three kinds of nodes energy distribution. So we think the different nodes energy distribution in the network has the weakest affect on the degree distribution.Figure 2
The degree distributionP(k) obtained by simulations with three kinds of ρ(E): same (0.5J), U[0,1], exp(-E) and by fitting line as dashed line, by the mean-field method as solid green line, where m=4, p=0.5, t=2000.The degree distributionP(k) obtained by simulations for three kinds of node energy distribution ρ(E) and by fitting line as dashed line; (a) p=0.25, (b) p=0.75; where m=4, t=2000.
(a)(b)


## 3.2. Connectivity Correlation

To clearly understand the influence ofρ(E) on the network connectivity and uncover the internal complexity of the topological structure, it is worth investigating the connectivity correlation through kE (the average degree of node with energy E) and knn(k) (the average degree of neighboring nodes of a given node with degree k). We find from Figure 4 that the node which has more energy has a larger degree. The node degree is linearly increased with node energy when ρ(E) is uniform distribution. But for the exponential distribution, there is an inward bend at the middle of the data curve that most high energy nodes carry much more links and a few of them keep relatively less links. It is because we can only perform a finite number of computation steps, and then possibly some nodes with high energy newly come into the network. There are a few hubs, that have much more links than the others nodes, emerging in the evolving process for the energy exponential distribution case. Thus the connectivity becomes more inhomogeneous when nodes energy is more heterogeneous.Figure 4
The relation between node degree and node energy obtained by simulations for two kinds of node energy distributionρ(E): U[0,1], exp(-E), where m=4, p=0.5.Connectivity correlation is also quantified by reporting the numerical value of the slope ofknn(k) as a function of K. We compute knn(k) which is defined as in [31]:(3.18)knn(k)=1Nk∑i∈Ωk(1k∑j∈Oikj),
where Ωk is the set of nodes with degree K of the amount Nk in the evolving WSNs. Oi is the set of linked neighbors of node i. In Figure 5, it is found that knn(k) is independent of K for nodes with large degree, that is, nodes with large k show no obvious biases in their connections. But there is a short disassortative region when k is relatively small, that is, nodes with low degree are more likely linked with the highly connected ones. Such phenomenon can be explained by the effect of network growth with energy preferential attachment and elements removals with antipreferential mechanism.Figure 5
The average degree of neighboring nodeknn(k) obtained by simulations for three kinds of node energy distribution ρ(E), where m=4, p=0.5.


## 3.3. Clustering Coefficient

We investigate the effect of node energy distribution on network’s cluster coefficient, which quantifies the extent to which nodes adjacent to a given node are linked [15, 31]. Let Ei denote the number of edges among the neighbor nodes of a selected node i with degree ki in the network; Ci is local clustering coefficient of node i. Then the clustering coefficient of the whole network is the average of all individual Ci. It is defined as follows: (3.19)C=1N∑iCi=1N∑iEiki(ki-1)/2.In Figure6, we give the clustering coefficient (C) changing by network size with three kinds of node energy distribution. C keeps very small value of 0.005 when node energy is same in the network. But when ρ(E) is exponential distribution, C keeps large value with the average value 0.185. The result indicates that nodes energy heterogeneity makes the network more clustering.Figure 6
The clustering coefficient obtained by simulations for three kinds of node energy distributionρ(E), where m=4, p=0.5.


## 3.4. Average Shortest Path Length and Network Efficiency

In WSN, the sensor nodes forward the data by multihops. The average path lengthL is defined to be the average length of the shortest paths between any two nodes in the network that is written as in (3.20). Usually we use it to measure the average hops among the nodes for data processing. Simultaneously we use the network efficiency E to measure how efficiently the information is exchanged over the network. Let dij denote the length of the shortest path between node i and node j. The efficiency between node i and j is assumed to be inversely proportional to the shortest distance: eij=1/dij. With this definition, when there is no path between i and j, dij=∞. The global efficiency of the network is defined as the average of the efficiencies over all couples of nodes. Its calculation can be defined as (3.21):(3.20)L=1N(N-1)∑i≠jdij,(3.21)E=1N(N-1)∑i≠j1dij.SinceL and E characterize the ability of two nodes to communicate with each other, the smaller L and the larger E mean fewer hops and less energy consumption for data processing. In Figures 7 and 8, we plot the average shortest path length (L) and network efficiency (C) with evolving time step t, which denoted network size, for three kinds of node energy distribution. We observe that L increases, and E decreases with the network size increasing. We also find, by the same evolving time step t, that the network obtains the smallest L and the largest E when ρ(E) is exponential distribution among the three kinds of ρ(E). Conversely, L is the largest and E is the smallest when node energy is same in the network for the same network size. The results verify that nodes in energy inhomogeneous networks are more efficient to communicate with others.Figure 7
The average shortest path length obtained by simulations for three kinds of node energy distributionρ(E), where m=4, p=0.5.Figure 8
The network efficiency obtained by simulations for three kinds of node energy distributionρ(E) where m=4, p=0.5.


## 4. Conclusion

In this paper, we have addressed a novel topology evolution model for wireless sensor networks. A notion of energy-aware mechanism combined with additions and removals of link and node has been first defined to characterize the evolution model of WSNs. Subsequently, by using mean-field approach, numerical calculation shows the network evolving into the scale-free state with a horse-head-like initial section. Finally, experimental simulations have been employed to demonstrate the effectiveness of the results derived in this paper. Node energy distribution has a weak effect on the degree distributionP(k) but it has much effect on the network internal topological characterizations. The node which has more energy will have more degrees for balancing energy consumption, and the model exhibits the nontrivial disassortative degree correlation as a natural property of network evolution. In addition, the connectivity is tighter and the network is higher clustering for the sensor network system in which node energy is more heterogeneous. Then, from the perspective of the average path length and the network efficiency, we find that, when node energy distribution is more heterogeneous, the network enjoys better performance in energy efficiency for transmitting data. The analysis of the robustness against the random failures and intentional attacks for the proposed model is beyond the scope of the current work and is left for future investigations.This model articulates the topology dynamics of the real WSNs and provides some useful guidelines for constructing WSNs.



---

*Source: 281465-2011-09-15.xml*