A Novel Node Importance Evaluation Method Based on Agglomeration Contraction Principle for Wireless Sensor Networks

Abstract

The node importance evaluation based on removal of nodes and their incident links cannot accurately reflect the importance of the nodes, because such approach may change the topology of the network, and even split the network into several disconnected parts. To solve this problem, we propose a novel node importance evaluation method based on agglomeration contraction principle. This method does not require the node being evaluated to be removed from the network; thus, it may not cause network fracture. With this method, aided by spectral analysis, the vital gateway nodes can be identified by using the nontrivial eigenvectors of the Laplace matrix of the network diagram. Then, a formula to estimate the importance of particular individuals within the network is proposed; moreover, the betweenness centrality and the positions of nodes are taken into consideration. At last, using some superenergy nodes to provide targeted protection for the vital gateway nodes in the network, the life of the network can be prolonged and the robustness of the system improved effectively. Above all, with this method, the number of nodes to be evaluated in a network can be reduced, and the computation decreased accordingly. Final experiments verify the efficiency of the proposed method and the result is consistent with our intuitive judgments.

1. Introduction

With the rapid growth of information technology and increasing popularity of wireless sensor networks, the reliability of such networks is attracting more and more researchers' attention. Many methods have been developed for the investigation and analysis of these networks. For the analysis of a wireless sensor network's reliability, one of the most important issues is to extract the most important, central nodes [1–5] in the network. This is important because in network management, it is vital for the manipulator to know in advance the components whose failure may seriously affect performance of the whole network. The failure of central node, due to intentional attacks or random failures, may occur frequently in wireless sensor networks, and such failure affects the network reliability seriously. Fortunately, there is an effective approach to solve this problem. The key to this approach is to determine the vital central nodes and put more protection on them to reduce their failure rates.

Compared with finding the optimal route from the source node to the sink, finding the most vital node in a network is not exciting. Currently, the number of such evaluation methods is quite limited. Meanwhile, most of the available methods [6–9] are based on the principle that the most vital node is the one whose fault may result in a large decrease in network's performance. Therefore, in the process of node importance evaluation, the nodes should be struck and removed in turn from the network. The disadvantage of such methods is that the topological importance of nodes cannot be distinguished efficiently when the network is split into several disconnected parts. In this paper, based on the agglomeration contraction principle, we propose a novel node importance evaluation method. This method does not require the node being evaluated to be removed from the network; thus, it may not cause network fracture. At the same time, this method can reduce the number of nodes to be evaluated in a network and decrease the computation accordingly.

The rest of this paper is organized as follows. The related work is summarized in Section 2. Section 3 introduces the model in our work. We present our novel node importance evaluation strategy and the analysis of its computation complexity in Section 4 and Section 5, respectively. Section 6 presents and discusses the experimental results. Finally, the conclusion is drawn in Section 7.

2. Related Work

The problem of finding the most vital node in a network was defined by Corley and Sha in 1982. In [10], Corley and Sha proposed an evaluation method, in which the most vital node is the one whose removal may largely increase the distance between the source and the destination nodes. More precisely, they considered the more general problem of finding the k most vital nodes in a network and gave an exponential algorithm for solving this problem. In [11], Chen et al. presented an evaluation method using spanning trees in which the most vital node is the one whose removal most greatly reduces the number of spanning trees.

Brodka et al. proposed a node position evaluation function in [12]; the importance of a node in a weighted network, expressed by this function, tightly depends on the strength of the relationships that this individual node maintains as well as on the node positions of their acquaintances. In other words, the position of a node is inherited from others and the level of inheritance depends on the activity of the members directed to this node, that is, intensity of common interaction, cooperation, or communication. In [13], based on email communication, a new node importance evaluation method is presented by Kazienko et al. Compared with the Brodka strategy, this measure takes into account not only the activity of the direct connections between nodes but also the quality of the connections.

Musial et al. analyzed the general advantages and disadvantages of different metrics in [14]. Some metrics are more general and contain more information about the node's neighborhood or the entire network, whereas the others reflect rather local character of the node. In [15], a method for evaluating node importance in communication network is proposed. This method defines the most vital node as the one whose contraction results in the largest increase of the network agglomeration. So if the degree of a node is high or its position is pivotal, the network agglomeration after contraction is high and then the node is important.

This paper makes the following contributions. First, based on spectral method, the gateway nodes of a network can be found by using the nontrivial eigenvectors of the Laplace matrix, which is an n-dimensional real symmetric matrix extracted from the base network. Second, a novel method to evaluate the degree of gateway node's topological importance is proposed based on agglomeration contraction principle. This method can find the vital gateway nodes in a network quickly. At last, using some superenergy nodes to protect the vital gateway nodes in a network, unwanted early deaths of the vital gateway nodes can be avoided, and hence the life of network can be prolonged and the robustness of system improved effectively.

3. The Model

Wireless sensor networks are applied in three major categories: periodic sensing, event driven, and query based. In this paper, the model is designed to adapt to features of event driven network. These sensors are fixed once they are deployed and their powers are limited. Sensor devices with a set of hardware monitors can monitor several environmental conditions. Each sensor node is a fully autonomous computation and communication device, characterized as the limited energy (battery), the poor processing capabilities, and the limited memory space. There is a static sink in network to collect data and act as a gateway for the network. Sensor node utilizes wireless radio resources to communicate with its one-hop neighbors and relay data to the sink in a multihop fashion. Meanwhile, the sensor nodes have no global knowledge of network.

3.1. The Communication Energy Consumption Model

In this paper, we use the radio model [16] to analyze energy consumption of sensor nodes. For transferring k-bits data message from the source node to the target node, the energy consumption of source node and target node is presented in (1) and (2), respectively.

Transmitting energy consumption model is as follows:

$$\begin{array}{cc}& E_T\left(k,d\right)=\{\begin{array}{cc}{E}_{Tx}\times k+a\times k\times d^{\mathrm{2}}\hfill & d\le d_{\mathrm{0}}\hfill \\ E_{Tx}\times k+b\times k\times d^{\mathrm{4}}\hfill & d>d_{\mathrm{0}}.\hfill \end{array}\end{array}$$

(1)

Receiving energy consumption model is as follows:

$$\begin{array}{cc}& E_R\left(k\right)=E_{Rx}\times k.\end{array}$$

(2)

The total energy consumption for transmitting k-bits data from node i to node j is

$$\begin{array}{cc}& E_{ij}\left(k,d_{ij}\right)=E_R\left(k\right)+E_T\left(k,d_{ij}\right),\end{array}$$

(3)

where d denotes the distance between the two sensor nodes; $E_T(k,d)$ in (1) is the total dissipated energy in the transmitter of source node; $E_R(k)$ in (2) represents the energy cost incurred in the receiver of target nodes; $E_{Tx}$ and $E_{Rx}$ denote the per bit energy dissipations for transmission and reception, respectively. In order to maintain an acceptable signal-to-noise ratio, the free-space propagation model and the two-ray ground propagation model are used to approximate the path loss sustained. a and b mean the two different amplifier parameters corresponding to these two models. When d is less than or equal to the threshold transmission distance $d_{\mathrm{0}}=\sqrt{a/b}$ , the free-space model is employed, and transmit amplifier parameter corresponding to this model is a. When d is greater than the threshold transmission distance $d_{\mathrm{0}}=\sqrt{a/b}$ , the two-ray model is applied, and transmit amplifier parameter corresponding to this model is b. For all experiments throughout the paper, we assumed parameters are set as in [16]: $E_{Tx}=E_{Rx}=50$  nJ/bit,   $a=\mathrm{100}$  pJ/b/m², $b=\mathrm{0.013}$  pJ/b/m⁴, and $d_0=\sqrt{a/b}\approx \mathrm{90}$  m.

3.2. Neighbor Information Table

In this paper, wireless sensor networks modal which is the same as in [16] is adopted and has the following properties:

• (i)

all sensor nodes are fixed and have a unique ID address;

(ii)

all sensor nodes are energy constrained with a uniform initial energy accusation;

(iii)

all sensor nodes have two omnidirectional antennas, one for transmitting packets and the other for receiving packets.

Meanwhile, each sensor node needs to build its own neighbor information table. Every neighbor information table should save the information as follows:

• (i)

the ID addresses of the current node and its neighbor nodes;

(ii)

the residual energy of the current node and its neighbor nodes;

(iii)

the position information of the current node and its neighbor nodes;

(iv)

the shortest route from the current sensor node to the sink.

4. Node Importance Evaluation Strategy

Since sensor nodes with their spontaneous and social behavior are hardly predictable, the problem of assessing the node importance becomes very complex. Node importance is a measure that reflects the characteristics of the node's neighborhood. Its value for the given individual respects both node positions of the nearest acquaintances and the level of activity of the neighbors directed to this node. Since the greater vital node has more valuable, we can focus our activities like querying network information or adding close managing solely on them. In this section, we propose a strategy to find the vital nodes in wireless sensor networks. First, using the spectral method, the network agglomerations can be found. Then according to the agglomerations contraction principle, we can get a backbone network which extracted from the base wireless sensor networks. Finally, the vital nodes in backbone network can be found by using the novel node importance evaluation formula proposed in this paper.

4.1. How to Find the Network Agglomeration

Spectral analysis is a clustering method and is a branch of algebraic graph theory that applies various matrix decompositions to study graph properties. Spectral methods derived from spectral analysis have aroused extensive attention of academia in recent years, due to their solid theoretical foundation, as well as the good performance of clustering. The word spectral refers to the spectrum of a network, which is given by the eigenvalue decomposition of Laplacian matrix corresponding to the network graph. In short, based on spectral analysis, we can draw the conclusion that the Laplacian matrix associated with the undirected network graph can be used in various areas of discrete mathematics, with interpretation in several physical and chemical problems. The eigenvalues of the Laplacian matrix have been extensively characterized in terms of topological features of the network graph. Eigenvectors, as other important statistics of the Laplacian matrix, also provide significant further information about network graph properties, for example, network partitioning, synchronization design, and optimal network resource allocation.

Consider an undirected network graph G which has n nodes and does not have loop or multiple edge. The nodes on graph G are labeled with $1,\dots ,n$ . The Laplacian matrix associated with G is a $n\times n$ matrix $L=({\mathcal{l}}_{ij})$ , whose elements are given by

$$\begin{array}{cc}& {\mathcal{l}}_{ij}=\{\begin{array}{cc}\mathrm{\hspace{0.17em}\hspace{0.17em}}-\mathrm{1}\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}i\ne j\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{and there is an edge}\hfill \\ \hfill & \text{between two nodes}\hfill \\ \mathrm{0}\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}i\ne j\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{and there is not an edge}\hfill \\ \hfill & \text{between two nodes}\hfill \\ {\displaystyle \sum }_{j=\mathrm{1}}^n\left|{\mathcal{l}}_{ij}\right|\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}i=j.\hfill \end{array}\end{array}$$

(4)

One of the basic results for Laplacian matrix is that L is a symmetric positive semidefinite matrix. Hence the eigenvalues for L can be ordered as ${\lambda }_{\mathrm{1}}\le {\lambda }_{\mathrm{2}}\le \cdots \le {\lambda }_{n-\mathrm{1}}\le {\lambda }_n$ . Observe that ${\lambda }_{\mathrm{1}}=\mathrm{0}$ , with corresponding eigenvector equal to $(\mathrm{1,1},\dots ,\mathrm{1}{)}_{\mathrm{1}\times n}$ . It is known that ${\lambda }_{\mathrm{2}}=\mathrm{0}$ if and only if G is disconnected. Among all eigenvalues of L, the most popular one is the ${\lambda }_{\mathrm{2}}$ , and the reason is that the number of times $\lambda =\mathrm{0}$ repeatedly appears equal to the number of connected components of G.

The Laplacian matrix L has the special property. In an undirected network with an apparent agglomeration structure, L has a certain number ( $m-1$ ) of eigenvalues close to 0, where m is the number of well-defined network agglomeration. The remaining eigenvalues are far away from 0. The eigenvectors associated with these $m-1$ nontrivial eigenvalues ( ${\lambda }_{\mathrm{2}},{\lambda }_{\mathrm{3}},\dots ,{\lambda }_m$ ) also have a characteristic structure: the components corresponding to the sensor nodes within the same agglomeration have very similar values $x_i$ ; so that, as long as the partition is sufficiently sharp, the profile of each eigenvector sorted by component value is step like. The number of steps in the profile corresponds again to the number of network agglomeration. Using the nontrivial eigenvector $x=(x_{\mathrm{1}},x_{\mathrm{2}},\dots ,x_n)$ associated with nontrivial eigenvalue ${\lambda }_{\mathrm{2}}$ , we define a $n\times n$ agglomeration spacing matrix $D=(d_{ij})$ , whose elements are given by

$$\begin{array}{cc}& d_{ij}=\{\begin{array}{cc}\left|x_i-x_j\right|\hfill & i\ne j\hfill \\ +\infty \hfill & i=j.\hfill \end{array}\end{array}$$

(5)

Simultaneously, to test whether a particular division is meaningful, we define a “modularity” Q as follows. Let $e_{ij}$ be the fraction of edges in network that connect vertices in group i to those in group j, and let $a_i={\sum }_j{e}_{ij}$ . Then $Q={\sum }_i(e_{ii}-a_i^{\mathrm{2}})$ is the fraction of edges that fall within agglomerations, minus the expected value of the same quantity if edges fall at random without regard to the agglomeration structure. Taking advantage of this definition, we define a $n\times n$ modularity incremental matrix $\Delta Q=(\Delta Q_{ij})$ , whose elements are given by

$$\begin{array}{cc}& \Delta Q_{ij}=\{\begin{array}{cc}\frac{\mathrm{1}}{\mathrm{2}m}-\frac{k_{ii}{k}_{jj}}{{\left(\mathrm{2}m\right)}^{\mathrm{2}}}\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}i,j\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{are connected}\hfill \\ \mathrm{0}\hfill & \text{otherwise},\hfill \end{array}\end{array}$$

(6)

where m is the number of edges in network. Using the definition of $a_i={\sum }_j{e}_{ij}$ , we can get the following formula:

$$\begin{array}{cc}& a_i={{\displaystyle \sum }}_j{e}_{ij}=\frac{k_{ii}}{\mathrm{2}m}.\end{array}$$

(7)

Based on these properties, we propose a spectral method to find the agglomeration of a network graph. The specific implementation steps are as follows.

Step 1.

Calculate the initial agglomeration spacing matrix $D=(d_{ij})$ , modularity incremental matrix $\Delta Q=(\Delta Q_{ij})$ , and $a_i$ according to (5), (6), and (7).

Step 2.

Select the smallest $d_{ij}$ from agglomeration spacing matrix   $D$ , if the corresponding element $\Delta Q_{ij}$ from modularity incremental matrix $\Delta Q$ is a positive number, merging the two small agglomerations (i and j) together. Then update the matrices    $D=(d_{ij})$ and $\Delta Q=(\Delta Q_{ij})$ as in the following rules. Remove the ith row and column of the matrices    $D$ and $\Delta Q$ ; update the jth row and column of the matrices   $D$ and $\Delta Q$ according to

$$\begin{array}{cc}& d_{jk}^{*}=d_{kj}^{*}=\{\begin{array}{cc}\min (d_{ik},d_{jk})\hfill & k\ne j\hfill \\ +\infty \hfill & k=j,\hfill \end{array}\\ \Delta Q_{jk}^{*}=\{\begin{array}{cc}\Delta Q_{ik}+\Delta Q_{jk}\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}k\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{is connected to}\hfill \\ \hfill & \text{both}\mathrm{\hspace{0.17em}\hspace{0.17em}}i\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{and}\mathrm{\hspace{0.17em}\hspace{0.17em}}j\hfill \\ \Delta Q_{ik}-\mathrm{2}{a}_j{a}_k\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}k\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{is connected to}\hfill \\ \hfill & i\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{but not to}\mathrm{\hspace{0.17em}\hspace{0.17em}}j\hfill \\ \Delta Q_{jk}-\mathrm{2}{a}_i{a}_k\hfill & \text{if}\mathrm{\hspace{0.17em}\hspace{0.17em}}k\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{is connected to}\hfill \\ \hfill & j\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{but not to}\mathrm{\hspace{0.17em}\hspace{0.17em}}i.\hfill \end{array}\end{array}$$

(8)

Step 3.

Update the variables $a_i^{*}$ , $a_j^{*}$ as follows: $a_i^{*}=\mathrm{0}$ , $a_j^{*}=a_i+a_j$ , and increment Q by $\Delta Q_{ij}$ .

Step 4.

Repeat Step 2 and Step 3 until all the elements $\Delta Q_{ij}$ in modularity incremental matrix are a nonpositive.

4.2. Network Agglomeration Contraction Principle

Usually, the number of nodes distributing randomly in the fixed bounded region can be regarded as a statistic process obeying Poisson distribution. The network derived from the statistical Poisson distribution has such character; that is, the spatial distribution of nodes in the target region is inhomogeneous, as shown in Figure 1(a).

Figure 1

(a) Nodes nonhomogeneously dispersed. (b) Agglomeration of network dispersed.

We can call this problem as the agglomeration phenomenon in nonhomogeneous network. In Section 4.1, we propose a spectral method to find the agglomeration in wireless sensor networks. With this method, the agglomerations can be identified from a network quickly and effectively. Considering the distributions of agglomeration in wireless sensor networks, as shown in Figure 1(b), we can see that the nodes in agglomeration are deployed more densely. Meanwhile the mutual relationships between nodes in agglomeration are stronger; that is, communication between nodes is more intensity, and this result is also consistent with our intuitive judgment.

In order to get the backbone network extracted from the base weighted graph, we propose an agglomeration contraction strategy. In this strategy, the agglomeration contracts into a new special node called “organ node”; the node that does not belong to any agglomeration will be called “gateway node” and remain unchanged in the base weighted graph. The graphical representation of agglomeration contraction is shown in Figure 2(a).

Figure 2

(a) The process of agglomeration contraction. (b) The backbone network which extracted from the base weighted graph.

In the process of contraction, all the sensors in agglomeration will be replaced by a new organ node and all the edges within agglomeration will be deleted. The edges between the gateway nodes will remain unchanged in backbone networks. The edges between the gateway node and the node lying in the agglomeration will amend in the following way. If there exists at least one node in the agglomeration connections with the gateway node in the original weighted graph, so there exists an edge between the organ nodes which is formed by this agglomeration contraction and the gateway node in the backbone networks, and the weight of this edge is equal to the smallest one of the edges between this gateway node and the node in the above-mentioned agglomeration. The edges between the nodes lying in different agglomerations will be modified in this manner; if there exists at least one edge among the nodes lying in different agglomerations, so there exists an edge between the organ nodes which are formed by different agglomeration contraction in the backbone networks. The weight of this edge is equal to the smallest one of the edges between the nodes lying in the above-mentioned different agglomerations. By this way, we can get the backbone network after contraction (as shown in Figure 2(b)).

Because the nodes inside organ node are more densely deployed and the mutual relationships are stronger, the question of organ node which cannot work effectively due to the residual energy will be solved easily by using the method of internal node rotation. Hence the organ nodes are very robust and do not need extra protection coming from the network operator. This is why the organ nodes do not join in the process of node importance assessment. However, the gateway nodes play an important role in connecting organ nodes; when one gateway node fails, some organ nodes follow quickly. This will cause network fragmentation and generates surveillance blind area. So the operator should reevaluate the importance of gateway nodes and provide extra protection for the vital gateway nodes in order to increase physical life of network; that is, it is also an effective approach to increase the reliability of network that the vital gateway nodes obtained more attention to reduce their failure rate.

4.3. Node Importance Evaluation Formula

The importance of nodes is a measure which tightly depends on the strength as well as quality of the relationships that this individual maintains and reflects the characteristics of the node's positions and the activity of the node's neighbors. In this section, we propose an evaluation formula, which enables us to estimate how valuable the particular individual within the weighted network is; moreover, the average path length and the position of a member are taken into consideration. This evaluation formula is defined as

$$\begin{array}{cc}& C\left(i\right)=\frac{{\sum }_{j\ne i,k\ne i}\left(g_{jk}\left(i\right)+d_{jk}\right)}{\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{\hspace{0.17em}\hspace{0.17em}}\left(n-\mathrm{1}\right)\left(n-\mathrm{2}\right)/\mathrm{2}},\end{array}$$

(9)

where $n>\mathrm{2}$ , $g_{jk}$ is the number of shortest routes between node j and node $k\hspace{0.17em}\hspace{0.17em}(j\ne k)$ ; $g_{jk}(i)$ is the number of shortest routes between node j and node k passing though the node i; $d_{jk}$ is the length of the shortest routes between node j and node k when the node i fails; n is the number of the nodes in the networks.

4.4. Node Importance Evaluation Algorithm

Combining the character of practical use of wireless sensor networks, a novel node importance evaluation strategy is proposed. This strategy is divided into two parts, the first part is to find the backbone network with the help of agglomeration contraction principle. Its specific implementation steps are as follows. First, the operator distributes sensor nodes on a fixed bounded monitor region S according to the Poisson process with fixed Poisson ratio. Then the inquiry information packets are used for the initialization of the whole network. Each node should build its own neighbor information table during the process of initialization and transmit its neighbor information table to the sink at the end of initialization. The sink uses the information obtained from neighbor information table to build a Laplace matrix of the base network and uses the spectral method proposed in Section 4.1 to find agglomerations in the base network. At last, the sink extracts the backbone network from the base graph by using the agglomeration contraction principle. The second part of this strategy is to find the vital gateway nodes in backbone network. Its specific implementation steps are as follows. (1) The sink constructs adjacent matrix of backbone network and marks out the “organ node” in backbone network; (2) the sink worked out the number of gateway nodes in backbone network and assigns the value to a local variable N; (3) for i from 1 to N, the sink uses Sum-W algorithm proposed in [17] to find the shortest routes between different nodes, passing through the node i, and assigns the number to a local variable $g_{jk}(i)$ ; (4) delete ith row and ith column of the adjacent matrix corresponding to the node i, then use Sum-W algorithm to find the shortest routes between different nodes, and count the length of the shortest routes, recorded as $d_{jk}$ ; (5) the sink figures out the number of variable $C(i)$ and assigns $i=i+1$ ; (6) if $i\le N$ , then return to Step 3. By this way, we can get the index of importance of all the gateway nodes.

Sum-W algorithm is another variation of Dijkstra algorithm; the difference between them is the way to assign the weights value in these edges in network. In Sum-W algorithm, assign the weights value of edges in network according the following rule:

$$\begin{array}{cc}& w_{ij}=\{\begin{array}{cc}\mathrm{0}\hfill & \text{if there is no edge between}\hfill \\ \hfill & \text{node}\mathrm{\hspace{0.17em}\hspace{0.17em}}i\mathrm{\hspace{0.17em}\hspace{0.17em}}\text{and}\mathrm{\hspace{0.17em}\hspace{0.17em}}j\hfill \\ \lambda E_{ij}(k,d_{ij})+\delta \frac{\mathrm{Re}\left(i\right)}{E\left(i\right)}\hfill & \text{otherwise.}\hfill \end{array}\end{array}$$

(10)

In this expression, λ and δ are partialness bias parameters, which satisfy $\lambda >\mathrm{0}$ , $\delta >\mathrm{0}$ , and $\lambda +\delta =\mathrm{1}$ . The different value of partialness bias parameters reflects the different shift toward $E_{ij}(k,d_{ij})$ and $\mathrm{Re}(i)/E(i)$ . $E_{ij}(k,d_{ij})$ denotes the total energy consumption for transmitting k bits data between nodes i and $j;\hspace{0.17em}\hspace{0.17em}\mathrm{Re}(i)$ is the residual energy of node i; $E(i)$ is the initial energy of sensor. When the weights value of edges in network is assigned according this rule ( $w_{ij}=\mathrm{1}$ , if there is an edge between i and j; $w_{ij}=\mathrm{0}$ , if there is no edge between i and j), Sum-W algorithm will be transmuted into Dijkstra algorithm.

5. Computation Complexity

By using the spectral method, our method can reduce the computational complexity and keep the property of fast convergence. The computing complex of this method is $O(n*(n-\mathrm{1}))$ , where n is the number of sensor nodes in randomly generated network. Comparing and evaluating the method proposed in this paper with other state-of-the-art methods like NICM which is based on node importance contribution matrix [2] and NINP which is based on network performance grads [1], it can be seen that the computing time of our method is also lower than that of existing algorithms. In Table 1, we provide the average CPU time of different strategy on various networks which has the same target area. The CPU time is recorded after each run of the algorithm is continued till the vital node is found. Each value in Table 1 is the average result of 5 independent runs.

Table 1

Average CPU time (s) of different strategy.

Different methods	The number of sensor nodes in randomly generated network
	25	30	35	40	45	50
NICM	0.453	0.461	0.496	0.524	0.561	0.596
NINP	0.352	0.367	0.413	0.446	0.467	0.483
Our method	0.026	0.023	0.035	0.038	0.042	0.045

From Table 1, it can be seen that our method can find the vital nodes in network with small calculation workload. However, NICM and NINP should calculate importance degree of each node in order to get the vital node; this factor may improve computation complexity of algorithm (in fact, the computing complex of NICM is $O(\mathrm{2}{n}^{\mathrm{2}})$ and the computing complex of NICM is $O(\mathrm{2}{n}^{\mathrm{2}}+n)$ , where n is the number of sensor nodes in randomly generated network). Meanwhile, these two algorithms are unsuitable for large scale network, because the calculation workload is too large to complete. In order to further test the performance of the proposed method, some comparative experiments have been conducted in the next section.

6. Experimental Validation

The correctness of the proposed method is validated by comparative experiments. In this section, we describe simulation environment, experiment setup, and performance metrics as well as experiment results.

6.1. Simulation Environment and Experiment Setup

The network monitor area is a square area, and some fixed sensor nodes are randomly distributed in this area. Meanwhile, only one static sink is deployed in network. The radio model discussed in [16] is adopted to analyze energy consumption of sensor nodes. A series of events are generated randomly. Position and occurrence time are stochastic. Only the sensor nodes in event areas monitor the physical environment and report the measurements to the static sink with data packets. All data packets are sent to the sink by the multihop routings which are found by Sum-W algorithm [17]. We performed the experiments with the network simulator platform NS-2 version 2.26. The main simulation parameters are listed in Table 2.

Table 2

The main simulation parameters.

Parameter	Value
Initial energy of super node	160 J
Communication radius of node	200 m
Transmit amplifier parameter a	100 pJ/bit/m2
Transmit amplifier parameter b	0.013 pJ/bit/m4
Data volume generated by one event	0.1 Mb
Initial energy of sensor	80 J
Number of sensor nodes	25~50
$E_{Tx}$ in formula (1)	50 nJ/bit
$E_{Rx}$ in formula (2)	50 nJ/bit
Length of the network	1000 m

6.2. Performance Metrics and Experiment Results

Under various environmental conditions, combining the distribution situation of the vital gateway nodes (in these comparative experiments, the vital gateway nodes in randomly generated network may be found firstly by utilizing the node importance evaluation method proposed in this paper), the robustness analysis of Sum-W algorithm is provided.

Network robustness under various experiment conditions is compared.

• (i)

Provide targeted protection for vital gateway nodes in network. In this case, we may use some superenergy nodes to provide targeted protection for the vital gateway nodes. The method puts a superenergy node in the vicinity of the vital gateway node.

(ii)

Systematically strike the vital gateway nodes in network. At such times, some vital gateway nodes will be removed from network directly.

(iii)

Randomly generate network without natural disturbance and human-caused disturbance.

(iv)

Provide random protection for nodes in network. In this application, the superenergy nodes will be scattered in network randomly.

(v)

Randomly strike the nodes in network. In this case, some sensor nodes in network will be randomly selected and struck.

In this section, the validity and reliability of node importance evaluation algorithm proposed by us will be completely proven. The following performance metrics are used to reflect the robustness of Sum-W algorithm under various hostile environmental conditions: (i) network lifetime; (ii) average hops of the shortest path; (iii) average delay of communication; (iv) the variation of residual energy of sensor node.

We choose the number of sensor nodes in network as the variate in simulations and use some superenergy nodes to provide targeted or random protection for vital gateway nodes. Meanwhile, the number of superenergy nodes used to protect vital gateway nodes is roughly 20% of the total number of nodes in network. The proportion of the nodes which are struck is about 10% of the total number of nodes in network. The number of nodes affects the performance of network remarkably. Therefore, using the number of nodes in network as the variate to shows how the strategy we proposed can effectively improve network robustness. In addition, each value dot in the following figures is the average of the simulation results in five networks.

6.2.1. Network Lifetime

In this section, the various experiment conditions proposed in Section 6.2 are used to reflect the lifetime of network. First, we vary the number of sensor nodes from 25 to 50 and compare the network lifetime achieved by Sum-W algorithm under the different experiment conditions. The results are shown in Figure 3. From Figure 3, we can see that the gap of network lifetime under the different experiment condition is very striking. Meanwhile, the results indicate that the condition of providing targeted protection for vital gateway nodes can improve the lifetime of network notably, and the condition of systematically striking the vital gateway nodes can cut down the lifetime of network obviously. This is because putting some superenergy nodes in the vicinity of vital nodes can strengthen the original key communication link and increase available bandwidth of the key link. At the same time, this way can expand network capacity significantly, reduce transmission distance of data packet, and avoid link congestion effectively. Hence, providing targeted protection for vital gateway nodes can increase the survivability and the lifetime of network efficiently. However, in the opposite case, systematically striking the vital nodes means some vital nodes may be removed from network directly. This way may increase network diameter. Hence, systematically striking the vital nodes can increase the transmission distance of data packet and cut down the lifetime of network notably. Randomly protecting or striking some sensor nodes in network would not significantly increase network diameter and affect the performance of key links in network. Thus, these ways have limited influences on the lifetime of network.

Figure 3

The lifetime of network under various experiment conditions.

6.2.2. Average Hops of the Shortest Path

Figure 4 shows the relation of the average hops of the shortest path under the different experiment conditions. From this figure, we can see that the average hops of the shortest path is significantly increased under the condition of systematically striking the vital gateway nodes in network. The reason is that the network diameter may be dramatic increased accordingly with the vital gateway nodes being removed gradually from network. This factor may improve the average hops of the shortest path in network notably. With the growth of node numbers, randomly protecting or striking some sensor nodes in network would not significantly change the diameter of network. Hence, these means have little impact on the average hops of the shortest path. However, when providing targeted protection for vital gateway nodes, the key links in network may get some special treatment. In short, the original of the shortest path in network has been reinforced. Thus, the average hops of the shortest path is no big change under this circumstance.

Figure 4

Average hops of the shortest path under various experiment conditions.

6.2.3. Average Delay of Communication

From Figure 5, it can be see that when the number of sensor nodes in network gradually becomes big, the average delay of communication under the condition of providing targeted protection for vital gateway nodes is the best one. The main reason is that some superenergy nodes have been put into the vicinity of the vital gateway nodes. This rule can improve the pass ratio of data packet in congestion area of network and expand the content of network. Meanwhile, by adding superenergy nodes in the vicinity of vital nodes to form the redundant link, diverging the date packet, increasing available bandwidth, and so on, this way enhanced the transmission efficiency of the entire network. Thus, the average delay of communication is reduced. It is noticeable that the average delay of communication under the condition of systematically striking the vital gateway nodes is the worst one. This is because this case improves the average hops of the shortest path, extends the length of the shortest path in network, and thus leads to the communication delay rapidly worsened. Meanwhile, from this figure, we can see that randomly putting some superenergy nodes in network has limited influences on the communication delay.

Figure 5

Average delay of communication under various experiment conditions.

6.2.4. The Variation of Residual Energy of Sensor Node

In this section, 100 sensor nodes are randomly deployed in $1000\hspace{0.17em}\text{m}\times 1000\hspace{0.17em}\text{m}$ square sensor field. Meanwhile, we suppose the initial energy of sensor node is 35  J. First, the vital gateway nodes in random network may be found by utilizing the method proposed in this paper. Then, a series of events are randomly generated in network, and the raw sensor data packets are sent to the sink using the multihop routing which are found by Sum-W algorithm. At last, compare the snapshots of residual energy of each sensor node when the network ruptured achieved under three different environmental conditions. One condition is providing targeted protection for five vital gateway nodes in network. Another condition is systematically striking the vital nodes by removing five vital gateway nodes from network. The last one is random generating network without natural disturbance and human-caused disturbance. As shown in Figure 6, under the condition of systematically striking, when the network ruptured, many sensor nodes still have much residual energy. This reveals that some sensor nodes consume their energy much more quickly than other sensor nodes. Under the condition of providing targeted protection for vital gateway nodes, when the network ruptured, the residual energies of almost all sensor nodes are very low. This reveals that the targeted protection strategy balances energy consumption well and all nodes consume their energy evenly; thereby the time when the first sensor node runs out of its energy is postponed, which is the reason why targeted protection strategy can improve network lifetime notably.

Figure 6

The residual energy of sensor node under various experiment conditions.

Above all, the simulation results show the correctness and effectiveness of the proposed node importance evaluation method. This is because the vital gateway nodes which are found by using this method really are the most vulnerable parts of network.

7. Conclusions

A novel node importance evaluation method based on agglomeration contraction principle is presented in this paper to extract the most vital gateway nodes in wireless sensor networks. This strategy uses the spectral method to find the original network agglomerations, and then according to the agglomeration contraction principle and the node importance evaluation formulation, the vital gateway nodes in wireless sensor networks can be found quickly. At last, the operator of network can use some superenergy nodes to provide targeted protection for vital gateway nodes; this strategy can improve the survivability of network notably. The final experiments show the correctness of the proposed node importance evaluation method, and this result is consistent with our intuitive judgments also.