# Survivability-aware topology evolution model with link and node deletion in wireless sensor networks.

1. IntroductionWireless sensor network (WSN) appears with the rapid development of microelectromechanical systems (MEMS), system on a chip (SoC), wireless communication, and low-power embedded technology, which brings a revolution of information perception. WSN is a multiple hops self-organizing network which is made of a large number of low-cost microsensor nodes deployed in the monitoring area by wireless communication. As the scale of WSN becomes larger and larger, the problem of coefficient, error, and attack tolerance arouses people's concern. Hence, it is necessary to find the solution.

In recent years, people pay more and more attention to the structure and dynamics of large complex networks [1]. Many new topology algorithms for wireless sensor networks have been presented due to the influence the topology has on the lifetime and communication efficiency of a network. In [2], a complex networks-based energy-efficient evolution model for wireless sensor networks is proposed. In [3], the authors presented a local world evolving model for energy-constrained wireless sensor networks. In [4], an energy-aware topology evolution model with link and node deletion in wireless sensor networks is presented. In [5], an evolving model of network with aging sites was proposed according to the effect of aging on network structure presented in [6,7]. The model applies the algorithm proposed in [8-11] such as the mean field theory to the algorithm in [5]. In [12], the authors proposed a weighted local world evolving network model with aging nodes to make the previous model portray some complex networks more appropriately.

The models above are all involved in the energy of a node. And the topology of a WSN is closely related to it. However, what impacts the lifetime of a node is not only the energy. As a result, the paper takes the notion of survivability into account. Survival analysis refers to making an analysis and inference on the survival time of creatures and people according to the data from tests or investigations. With the continuous improvement of the theories and methods of survival analysis, survival analysis comes to be applied to some other fields such as the assessment of the lifetime of products.

Survival analysis has become another hot topic in recent years. Although it is proposed to solve some biology problems, people are focusing on its application to computer science [13]. For example, the articles [14-19] are trying to give a three-layer survivability analysis on the reliability of the WSN. As we all know, the WSN consists of plenty of inexpensive sensor nodes, which are not repairable and worthy of repairing. Therefore, the lifetime of the sensor nodes is limited. And the WSN is generally deployed in the severe environment, which will shorten the lifetime of the nodes. And then it is necessary to consider the survivability of the nodes when studying the topology of the WSN. So this paper applies the survivability of every node to the energy-aware topology evolution model with link and node deletion and then explores the topology of WSN.

The remainder of the paper is made of three sections. In Section 2, an algorithm of survival topology evolution model, which is based on [4], is proposed. In Section 3, the numerical experiments to present the features of the networks generated by the proposed algorithm are given. Finally, some concluding remarks are given in Section 4.

2. Model

The particular features of WSNs evolving networks can be captured in the present model. The model evolves from an initial WSN consisting of n0 nodes and [e.sub.0] edges.

2.1. Preferential Attachment. The survivability of the nodes in a WSN has an impact on the lifetime of the network, which will influence the topology of the network at the same time. As we all know, the survivability of a node is not only related to the energy of the node, but also involved in other factors such as the disturbance in the environment. The section is doing some researches on how the survivability of the nodes impacts the topology of a WSN. In other words, the model takes the energy of the node, the disturbance in the environment, and so on into account. Then, the iterative algorithm during the evolving process is outlined as follows.

At each time step, a new node is added to the system. And m (0 < m < [n.sub.0]) new links from the new node are connected to existing nodes [1]. We assume that the probability n; of a new node will be connected to node i depends on the connectivity [k.sub.i] and the survivability of the node i. In this paper, we define a function f(S(t)) to represent the relationship between the survivability of a node and its ability to be linked. The more survivability of a node is, the more ability it will have of being connected to the new coming nodes. Therefore, f(S(t)) must be an increasing function and the form may be S(t), [[S(t)].sup.2], [square root of S(t)], ln[S(f)], and so on. In this paper, we just set f([S.sub.i](t)) = [S.sub.i] (t). And the form of n is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

From [13], the survivability S(t) of a node is defined as the probability that the life T of the node exceeds the time t (t > 0):

S(t) = P(T [greater than or equal to] t). (2)

2.2. Links Deletion. At each time, with probability p (0 [less than or equal to] p < l),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; see [4]. We assume the value of the parameter p is related to the survivability S(t) of the node. In this paper, we assume the survivability of a node is related to the definition of the deletion rate p as follows.

We set a survival function threshold n (0 < n < 1). If the survivability of a node satisfies

S (t) = P (T [greater than or equal to] t) < n (3)

then the node will be removed. So the deletion rate of the node can be expressed as the probability that the survivability of the node is lower than the threshold n:

p = P[S(t) < n] = P {P(T [greater than or equal to] t) < n}. (4)

We first select a node i as an end of a deleted link with the antipreferential probability as

[PI]* ([k.sub.i]) = [[S.sub.i] (t)[[k.sub.i]].sup.-1]/[[SIGMA].sub.j][[[S.sub.j] (t) [k.sub.j]].sup.-1] (5)

The less energy the node has, the more probability it will have for being deleted.

Then node j is then chosen from the linked neighborhood of node i (denoted by [O.sub.i]) with probability [K.sup.-1.sub.i] [PI]*([k.sub.j]), where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. 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.

2.3. Degree Distribution. In complex networks, the degree distribution P(k), which indicates the probability that a randomly selected node has k connections, is a very important and useful factor to observe the features of networks and has been suggested to be used as the first criterion to classify real-world networks. In this paper, the mean field theory is adopted to give a qualitative analysis of P(k) for our survivability-aware evolving model with link and node deletions.

By the mean field theory, let [k.sub.i](t) be the degree of the ith node at time t, and then, in the limit of large t, the increasing rate of [k.sub.i](t) satisfies the following dynamical equation:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (6)

The first term in (6) accounts for the increasing number of links of the ith node by the preferential attachment due to the newly added node. The second item in (6) means the losing of links by antipreferential attachment during the evolving process.

From the mean field sense, we have

[summation over (j)][S.sub.j] (t)[k.sub.j] = N(t) * [bar.S](t) * (k(t)>, (7)

where [bar.S](t) is the expected value of the node survivability in the whole network; N(t) is the number of nodes at time t; (k(t)) is the average degree of the network at time t. For large t,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (8)

In this paper, we assume that the survivability of nodes is exponential distribution as the following:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (9)

where [t.sub.i] indicates the time a new node is added to the network and [lambda] ([lambda] > 0) is a parameter of the exponential distribution. Then the expected node survivability in the whole network is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (10)

Finally, we can get the simplified form of the dynamical equation:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (11)

2.4. Calculation

2.4.1. Case A(p=0). In thiscase, there are only link and node additions without link and node deletions in the evolving process. It is usually fit for topology discovery state of WSNs in which all nodes have enough survivability in the ideal environment. So [k.sub.i] (t) satisfies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (12)

With the initial condition [k.sub.i](t) = m, then we can get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (13)

The probability that a node has a connectivity which satisfies [k.sub.i]([t.sub.i]) < k is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (14)

where A = 2[lambda](1 - [e.sup.-[lambda]t])/([e.sup.-[lambda]] - 1)[e.sup.-[lambda]t].

Assuming that we add the node to the network at equal time intervals in evolving process for WSNs, the probability density at the time [t.sub.i] is P([t.sub.i]) = 1/([n.sub.0] + t). Therefore, we get

P([k.sub.i] < k)= 1/[[lambda]([n.sub.0] + t)[ ln (A + [e.sup.[lambda]t] - A k/m). (15)

The probability density function of the degree of a node is

[[partial derivative]P ([k.sub.i] < k)]/[partial derivative] = 1/[lambda]([n.sub.0] + t) -A(1/m)/[A+[e.sup.[lambda]t] - A(k/m)]. (16)

2.4.2. Case B (p [not equal to] 0). In this case, links and nodes in the evolving network model are not monotonously growing. Instead, links and nodes can be added in some occasions and removed in other cases.

At first, we assume the probability density of the threshold n is 1. Then we can obtain the expression of p from (4) and (9)

p = P[S(t) < n}

= P{n>P(T [greater than or equal to] t)} (17)

= 1-P{n-P(T [greater than or equal to] t)} = 1-[e.sup.-[lambda]t].

Here, we assume t [much greater than or equal to] [t.sub.i]. Then we can get (18) from 11)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (18)

By solving the differential equation (18), we can get the form of the solution to the differential equation as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (19)

where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (20)

With the same initial condition as Case A, [k.sub.i]([t.sub.i]) = m, the solution will be (21) after simplification. Consider

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (21)

where A = ([e.sup.-[lambda]] - 1)/2[lambda].

Then the probability that a node has a connectivity which satisfies [k.sub.i]([t.sub.i]) < k is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (22)

Assuming that we add the node to the network at equal time intervals in evolving process for WSNs, the probability density at the time [t.sub.i] is P([t.sub.i]) = 1/([n.sub.0] +t). Therefore, we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (23)

The probability density function of the degree of a node is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (24)

3. Simulation

In this section, we compute numerical results in the evolution of a network and compare them with simulation examples.

3.1. Case A (p= 0). The degree distribution P(k) is provided for different time t with fixed [lambda] = 0.3, [n.sub.0] = 50, m = 2 in Figure 1. According to (15), k must satisfy the following condition to guarantee nonnegativity of P(k), which is consistent with the other expressions:

k > m + m/A [e.sup.[lambda]t]. (25)

It indicates that the degree distributions P(k) are approximately power law as B-A model. Figure 1(a) shows that the network makes lower connectivity as t increases, because the scale of the network becomes larger with the increment of t. Although the probability of a node to be connected becomes bigger as time goes on, the number of nodes in the network becomes larger at the same time. Of course, the survivability of nodes becomes smaller as time goes on, which is also the reason of lower connectivity as t increases. Figure 1(b) shows that the degree distribution P(k) follows an approximate exponential decay with the increase of k and the rate of decay will be much faster with the growth of time.

The degree distribution P(k) is provided for different time [lambda] with fixed t = 1000, [n.sub.0] = 50, m = 2[lambda] = 0.3, [n.sub.0] = 50, m = 2 in Figure 2. It indicates that the network makes higher connectivity as [lambda] decreases. Figure 2(a) shows that when the survivability of the nodes in the network becomes lower with the increment of [lambda], the probability of the nodes to be connected will be higher, which is the same with the definition of (1). Figure 2(b) shows that the degree distribution P(k) follows an approximate exponential decay with the increment of k and the rate of decay will be much faster with the growth of [lambda].

The degree distribution P(k) is provided for different time [n.sub.0] with fixed t = 1000, [lambda] = 0.3, m = 2 in Figure 3. Figure 3(a) shows that the network yields higher connectivity as [n.sub.0] decreases. It is concluded that the degree distribution P(k) follows an approximate exponential decay with the increase of k and the rate of decay will be much faster with the growth of [n.sub.0].

The degree distribution P(k) is provided for different time m with fixed t = 1000, [lambda] = 0.3, [n.sub.0] = 50 in Figure 4. Figure 4(a) shows that with the increase of the value of m, the beginning of the curve gradually moves to right, which is determined from (25). It is also very easy to understand that the network makes higher connectivity as m increases. Hence, Figure 4(b) shows that the degree distribution P(k) follows an approximate exponential decay with the increase of P(k) and the greater the m is, the faster the rate of the decay will be from Figure 4.

3.2. Case B (p [not equal to] 0). The degree distribution P(k) is provided for different time t with fixed [lambda] = 0.3, [n.sub.0] = 50, m = 2 in Figure 5. According to (23), k must satisfy the following condition to ensure nonnegativity of P(k)

k > m + 2[me.sup.[lambda]] - 2mA[e.sup.[lambda]][e.sup.-[lambda]t]. (26)

It can be found that the degree distributions P(k) are approximately power law as B-A model because the survivability of the nodes will become lower as time goes on. Figure 5(a) shows that the network makes higher connectivity as t increases, because the scale of the network becomes larger with the increase of t, which is the same with Case A. In addition, the value of P(k) is higher when k is comparatively smaller due to the limitation to the lifetimes of nodes. Figure 5(b) shows that the degree distribution P(k) follows an approximate exponential decay with the increase of P(k).

The degree distribution P(k) is provided for different time [lambda] with fixed t = 1000, [n.sub.0] = 50, m = 2 in Figure 6. In Case B, the nodes and links are deleted according to the survivability of the nodes, so when the value of [lambda] becomes bigger, that is to say, the survivability of the nodes becomes lower, the nodes and its links will be easier to be deleted. Consequently, the values of P(k) are bigger at the beginning of the curves with the smaller [lambda]. According to (26), the curve with bigger value of [lambda] begins where the value of k is bigger. Due to the survivability, the values of P(k) with bigger [lambda] will become smaller with the increment of k. So some intersections will be shown in Figure 6(a). Figure 6(b) shows that the degree distribution P(k) follows an approximate exponential decay with the increase of P(k).

The degree distribution P(k) is provided for different time [n.sub.0] with fixed t = 1000, [lambda] = 0.3, m = 2 in Figure 7. Figure 7(a) shows that there is an inverse relationship between [n.sub.0] and P(k), which can also be seen from (24). Figure 7(b) shows that the degree distribution P(k) follows an approximate exponential decay with the increment of k and the rate of decay will be much faster with the growth of [n.sub.0].

The degree distribution P(k) is provided for different time m with fixed t = 1000, [lambda] = 0.3, [n.sub.0] = 50 in Figure 8. Figure 8(a) shows that the curves begin at different places, which is the same with Case A. The bigger the m is, the bigger the value of k at the beginning of the curve will be, which can also be seen in (26). Compared with Case A, the distance of the beginning points with different m becomes bigger, which results from the deletion of nodes and links according to the survivability of nodes. Figure 8(b) shows that the degree distribution P(k) follows an approximate exponential decay with the increase of P(k).

Compared with Case A, the degree distributions of Case B are bigger because the deletion makes the scale of the network in Case B smaller than that in Case A. And all the degree distributions P(k) follow the approximate exponential decay with the increment of k. The rate of the decay depends on the choice of different parameters.

The evolving algorithms for wireless sensor networks discussed in [2-4] are based on the energy of nodes. And this paper introduces the relationship between the survivability of nodes and the energy of nodes. The survivability of nodes is influenced by the battery consumption of the nodes, the disturbance in the environment, and so forth. It is easy to understand that the decrease of the energy of nodes gives rise to the decline of the survivability of the nodes.

It can reach some conclusions from the simulation above. It indicates that the degree distribution follows approximately power law. And the degree distribution increases with the decrease of the survivability. According to the relationship between survivability and energy, the conclusion is consistent with the conclusion in [2-4].

4. Conclusion

The paper proposes the algorithm of survivability topology evolution model. The model applies the survival analysis to the research on the topology of networks and presents the mathematical results. The lifetime of nodes has a great impact on the wireless sensor network made up of these nodes. So we consider the survival analysis of the nodes. Due to the battery consumption of the nodes, the disturbance in the environment, and so forth, the survivability of the nodes will change in real time, which will get rise to the real-time change of the topology of the WSN. Therefore, it is necessary to take the survivability of nodes into account when the topology of the WSN is studied.

According to the model, the simulation studies of the model are presented. From these results, it reaches the conclusion that the degree distributions P(k) are approximately power law as B-A model. When there is no deletion of nodes and links in the network, the lower the survivability of the nodes is, the bigger the values of P(k) will be. When there is a deletion of nodes and links according to the survivability of the nodes, the same consequence can be obtained. Moreover, the values of the degree distributions P(k) in Case B are bigger than those in Case A.

http://dx.doi.org/10.1155/2014/278629

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgments

The authors would like to thank the reviewers for their detailed comments on earlier versions of this paper. This work was supported by Shanghai Leading Academic Discipline Project (S30108, 08DZ2231100), funding of Shanghai University (sdcx2012058), funding of Shanghai Education Committee, funding of Key Laboratory of Wireless Sensor Network and Communication, Shanghai Institute of Microsystem and Information Technology, and Chinese Academy of Sciences, and funding of Shanghai Science Committee (12511503303).

References

[1] X. F. Wang and G. Chen, "Complex networks: small-world, scale-free and beyond," IEEE Circuits and Systems Magazine, vol. 3, no. 1, pp. 6-20, 2003.

[2] H. Zhu, H. Luo, H. Peng, L. Li, and Q. Luo, "Complex networks-based energy-efficient evolution model for wireless sensor networks," Chaos, Solitons and Fractals, vol. 41, no. 4, pp. 1828-1835, 2009.

[3] N. Jiang, H. Chen, and X. Xiao, "A local world evolving model for energy-constrained wireless sensor networks," International Journal of Distributed Sensor Networks, vol. 2012, Article ID 542389, 9 pages, 2012.

[4] X. Luo, H. Yu, and X. Wang, "Energy-aware topology evolution model with link and node deletion in wireless sensor networks," Mathematical Problems in Engineering, vol. 2012, Article ID 281465, 14 pages, 2012.

[5] S. N. Dorogovtsev and J. F. F. Mendes, "Evolution of networks with aging of sites," Physical Review E: Statistical Physics, Plasmas, Fluids, and Related Interdisciplinary Topics, vol. 62, no. 2, pp. 1842-1845, 2000.

[6] H. Zhu, X. Wang, and J. Zhu, "Effect of aging on network structure," Physical Review E: Statistical, Nonlinear, and Soft Matter Physics, vol. 68, no. 5, Article ID 056121, pp. 561211-561219, 2003.

[7] K. B. Hajra and P. Sen, "Aging in citation networks," Physica A: Statistical Mechanics and its Applications, vol. 346, no. 1-2, pp. 44-48, 2005.

[8] A. Barabasi, R. Albert, and H. Jeong, "Mean-field theory for scale-free random networks," Physica A: Statistical Mechanics and its Applications, vol. 272, no. 1, pp. 173-187, 1999.

[9] K. B. Hajra and P. Sen, "Modelling aging characteristics in citation networks," Physica A: Statistical Mechanics and its Applications, vol. 368, no. 2, pp. 575-582, 2006.

[10] X. Geng and Y. Wang, "Degree correlations in citation networks model with aging," Europhysics Letters, vol. 88, no. 3, Article ID 38002, 2009.

[11] S. N. Dorogovtsev, P. L. Krapivsky, and J. F. F. Mendes, "Transition from small to large world in growing networks," Europhysics Letters, vol. 81, no. 3, Article ID 30004, 2008.

[12] G. Wen, Z. Duan, G. Chen, and X. Geng, "A weighted local-world evolving network model with aging nodes," Physica A: Statistical Mechanics and its Applications, vol. 390, no. 21-22, pp. 4012-4026, 2011.

[13] Z. S. Ma and A. W. Krings, "Survival analysis approach to reliability, survivability and Prognostics and Health Management (PHM)," in Proceedings of the IEEE Aerospace Conference (AC '08), pp. 1-20, IEEE, March 2008.

[14] Z. Ma and A. W Krings, "An outline of the three-layer survivability analysis architecture for strategic information warfare research," in Proceedings of the 5th Annual Cyber Security and Information Intelligence Research Workshop: Cyber Security and Information Intelligence Challenges and Strategies (CSIIRW '09), A. W. Krings and F T Sheldon, Eds., vol. 28, April 2009.

[15] Z. S. Ma and A. W. Krings, "Dynamic hybrid fault modeling and extended evolutionary game theory for reliability, survivability and fault tolerance analyses," IEEE Transactions on Reliability, vol. 60, no. 1, pp. 180-196, 2011.

[16] Z. S. Ma and A. W. Krings, "Dynamic hybrid fault models and the applications to wireless sensor networks (WSNs)," in Proceedings of the 11th ACM International Conference on Modeling, Analysis, and Simulation of Wireless and Mobile Systems (MSWiM '08), pp. 100-108, October 2008.

[17] Z. S. Ma, "A new life system approach to the prognostic and health management (PHM) with survival analysis, dynamic hybrid fault models, evolutionary game theory, and three-layer survivability analysis," in Proceedings of the IEEE Aerospace Conference (AC '09), pp. 1-20, IEEE, March 2009.

[18] Z. S. Ma and A. W. Krings, "Multivariate survival analysis (I): shared frailty approaches to reliability and dependence modeling," in Proceedings of the IEEE Aerospace Conference (AC '08), pp. 1-21, IEEE, March 2008.

[19] Z. Ma, A. W. Krings, and R. E. Hiromoto, "Multivariate survival analysis (II): an overview of multi-state models in biomedicine and engineering reliability," in Proceedings of the 1st International Conference on BioMedical Engineering and Informatics: New Development and the Future (BMEI '08), pp. 536-541, IEEE, May 2008.

Yanliang Jin, (1) Xuqin Zhou, (1) Zhishu Bai, (1) Wei Ma, (1) Lina Xu, (1) Zhuo Wu, (1) Su Ki Ooi, (2) and Yue Liu (3)

(1) Key Laboratory of Specific Optical Fiber and Light Access of Ministry of Education, Shanghai University, Shanghai 200072, China

(2) National ICT Australia, Victoria Research Laboratory, Department of Electrical and Electronic Engineering, The University of Melbourne, Parkville, VIC 3010, Australia

(3) School of Computer Engineering and Science, Shanghai University, Shanghai 200072, China

Correspondence should be addressed to Yanliang Jin; jinyanliang@staff.shu.edu.cn

Received 26 December 2013; Revised 24 March 2014; Accepted 4 April 2014; Published 28 April 2014

Academic Editor: Jianshe Wu

Printer friendly Cite/link Email Feedback | |

Title Annotation: | Research Article |
---|---|

Author: | Jin, Yanliang; Zhou, Xuqin; Bai, Zhishu; Ma, Wei; Xu, Lina; Wu, Zhuo; Ooi, Su Ki; Liu, Yue |

Publication: | International Journal of Distributed Sensor Networks |

Article Type: | Report |

Date: | Jan 1, 2014 |

Words: | 4345 |

Previous Article: | Efficient wireless vibration data sensing and signal processing technique based on the android platform. |

Next Article: | A dynamic users' interest discovery model with distributed inference algorithm. |

Topics: |