Sage Journals: Discover world-class research

Abstract

Power-Law topology has been proved to be an effective technique to improve fault tolerance. With the motivation of construct reliable topology for wireless sensor networks, a Power-Law Evolving Model (PLEW) of wireless sensor networks by stochastic placement is proposed in this article. In a dynamic evolving process of Wireless Sensor Networks, there are four types of events as follows: adding new nodes, nodes failure, adding new links, and links failure. The dynamics of nodes and links are integrated into the evolving model consequently. By using the continuum theory, the theoretical computing and simulated results show that the degree distribution of this model follows a power law. The scale-free properties revealed in this model can be applied into the scenarios required high dependability, such as national defense or survivability systems.

Keywords

Wireless Sensor Networks Scale-Free Power-Law Continuum Theory Evolving Model

1. Introduction

Recent advances in nanotechnology have made it possible to develop a large variety of low power devices that integrate sensing, special purpose computing, and wireless communications capabilities. A Wireless Sensor Networks (WSNs) is a collection of many small devices, each with sensing, computation, and communication capability. It has many potential applications, such as building surveillance, environmental monitoring, etc.

The sensor node placement in wireless sensor networks can be divided into deterministic and stochastic placement [1]. The deterministic placement requires that each sensor node be placed at predetermined coordinates, while in stochastic placement, the positions of the sensor nodes are determined by a probability density function (p.d.f.). In the latter placement, approximate positioning satisfies the probability density function, which causes low placement cost. Due to node failure and limited node power capacity, the nodes placement turns out to be extraordinarily important, and stochastic placement has been testified to be an effective fault tolerance technique in [1]. Also, the forms of stochastic placement can produce scale-free properties, where the degree of the nodes follows a power law.

In this article, we consider a complex wireless sensor network by stochastic placement based on [1]. By analyzing the dynamics of wireless sensor networks, a Power-Law Evolving Model (PLEW) is proposed, where the degree distribution shows scale-free properties. The rest of the article is organized as follows. In Section 2 we basically describe related work and our contribution. In Section 3 we introduce a classical BA scale-free model. In Section 4, the design of PLEW is discussed in detail. In Section 5 we conduct the theoretical analysis by using the continuum theory, as well as the simulation, followed by the conclusions in Section 6.

2. Related Work and our Contribution

In the past few years, more and more researchers have devoted their enthusiastic energy to explore and characterize the evolving mechanisms of complex natural network systems, such as the Internet [2, 3], the World Wide Web (WWW) [4], traffic networks [5], food webs [6], etc. Empirical research by using the statistical approach shows that these networks generally exhibit universal properties of complex networks, including small-world characteristic [7] and scale-free characteristic [8].

Due to the limit of the wireless transmission range, wireless sensor networks belong to spatial graphs, and not to rational graphs [9]. Whether wireless sensor networks have the characteristics like other complex natural network systems, such as the Internet or the World Wide Web? What are small-world effects and scale-free properties in wireless sensor networks, including the degree distribution, the path length, and clustering coefficient? How to model the dynamics of wireless sensor networks? In 2002, Jin and Symeon et al. [10] modeled mobile wireless sensor networks, which described the dynamics of the network and facilitated the understanding of the effect of the various events, and this is the original work, to the best of our knowledge. In 2003, Mika et al. [1] probed the scale-free properties of wireless sensor networks by using the probability density function; she has proved that the power-law placement can constitute good placement with a well-tuned control parameter. Helmy [9] investigated the small-world effects in wireless networks by randomly link re-wiring and link addition. In 2004, Sarshar et al. [11] first showed that only relying on the classical BA model cannot produce heavy-tailed degree distribution in complex ad hoc networks and P2P networks. He has proposed an evolving model which introduced the mechanisms of nodes deletion and links compensatory rewiring; Saffre et al. [12] successfully implemented the scale-free topology for pervasive networks, which conquered the difficulty by devising realistic connection protocols that would allow approximating scale-free topology on the sole basis of local information exchange. In 2005, Chen GuanRong modeled the complex Internet topology in his preeminent work [3], which captured the Local-World evolving dynamics. In 2007, Qin et al. [13] proposed a complex ad hoc network model with accelerated growth based on [11] and [14]; Wang et al. [15] designed a topology control algorithm, which introduced the scale-free properties into the topology of Wireless Sensor Networks to minimize transmission delay and increase robustness; Garbnato et al. [16] investigated the impact of scale-free topologies on Gossiping in the context of Wireless Sensor Networks; Chen Lijun et al. [17] presented an evolving model with equivalent growth of the nodes, which was based on the BA evolving model [8] and Local-World evolving model [18], and this model can improve the uniformity of the degree distribution; Brooks et al. [19] used Bernoulli probability matrices to analyze the random graphs model of mobile sensor networks, which presented an application for the security of sensor networks.

Due to unforeseen reasons, the topology of WSNs often changes. How to model the dynamics of topology is very meaningful for constructing reliable WSNs, improving fault tolerance, and the efficiency of routing. Actually, in real networks, there are five types of evolving events: adding new nodes, nodes failure, adding new links, links failure, and links re-wiring. We consider links re-wiring as the combination of adding new links and links failure, so we do not analyze links re-wiring in this article. However, in most works we have mentioned, they considered the issue of adding new nodes, adding new links, and links failure, except the work reported in [1] and [11]. In this article, we specially consider the nodes failure or randomly attack in WSNs, and use the continuum theory [8] and the similar method in [3, 11] to predict the exponent of degree distribution; then we conduct the simulation to verify the validity of our model.

3. BA Scale-Free Model [8]

3.1. Evolving Process

The evolving process of the classical BA scale-free model includes two ingredients as follows: equivalent growth of the nodes and the degree of preferential attachment. The equivalent growth implies that the dimension of the entire network grows continuously, is different from the small-world network and random network where the number of nodes is static; the degree of preferential attachment means adding new nodes incline to be attached with high-degree nodes. Based on the two aspects which have been mentioned, the evolving process of the BA model is carried out as follows:

3.1.1. Equivalent Growth

Starting with m₀ nodes, at every time step t we add a new node with m links that connect the new node to m different nodes already present in the network (m < m₀).

3.1.2. Preferential Attachment

The probability π _i that a new node will be connected to node i depends on the degree k_i of that node, so that $π_{i} = k_{i} / \sum k_{j}$ . After t time steps, the model leads to a random network with t + m₀ vertices and mt edges.

3.2. Analysis of Degree Distribution

In the BA model [8], the continuum theory was used to analyze the degree distribution. The rate at which a node acquires links is: $\partial k_{i} / \partial t = m k_{i} / \sum_{j} k_{j}$ , and $\sum_{j} k_{j} = 2 m t$ so we can get $\partial k_{i} / \partial t = k_{i} / 2 t$ , it gives $k_{i} (t) = m (t / t_{i})^{β}, β = 1 / 2$ . The probability that a node i has a degree smaller than $k P (k_{i} (t) < k) = P [t_{i} > m^{1 / β} t / k^{1 / β}]$ . Assuming that we add the nodes to the network at equal time intervals with the probability $P (t_{i}) = 1 / m_{0} + t$ , so

P [t_{i} > m^{1 / β} t / k^{1 / β}] = 1 - m^{1 / β} t / (k^{1 / β} (m_{0} + t))

we get the degree distribution:

P (k) = \partial P [k (i, t) < k] / \partial k = \frac{2 m^{1 / β} t}{m_{0} + t} \frac{1}{k^{1 / β + 1}}

, for large t (t → ∞),

P (k) \sim 2 m^{1 / β} k^{- γ}, γ = 1 / β + 1 = 3

4. Power Law Evolving Model by Stochastic Node Placement

4.1. Network Formalization Definition

In general, the nodes of WSNs are placed in a coordination in 2-D or 3-D euclidean space and the entire sensor network is formalized as a unit disk graph G = <V(G),E(G)>, where V(G) = {v1, v2, …,v3} is the set of nodes and E(G) the set of wireless links; range_vi is the max transmission range of sensor node v_i [20]. If the distance between vi and vj is less than range_vi, link(vi, vj) will exist. In real sensor networks, the transmission range of each node may not be a perfect disk. In this case, the network is a quasi-unit disk graph. Thus E(G) can be expressed as: $E (G) = {(v_{i}, v_{j}) : d (v_{i}, v_{j}) \leq r a n g e_{v_{j}}, v_{i}, v_{j} \in V (G)}$ , here we assume $| V (G) | = n, | E (G) | = m$ .

4.2. Network Parameters

The degree of nodes can describe the importance of nodes in the network. We define p(k) as the probability of the nodes which have k degree. A different network has a different p(k) function.

The network distance and diameter of the network can not make overall evaluation. We need to introduce the average path length. The graph G = <V(G),E(G)< is usually described by means of two parameters: the average path length L and the clustering coefficient C. The average path length L is defined as the minimum distance between any pair of nodes (i,j), averaged over all possible pairs, and showed as follows:

L = \frac{1}{\frac{1}{2} N (N + 1)} \sum_{i \geq j} d_{i j}

Considering the situation of non-connected graph, we define L as follows:

L^{- 1} = \frac{1}{\frac{1}{2} N (N + 1)} \sum_{i \geq j} d_{i j}^{- 1}

The clustering coefficient describes the aggregation level of the network, and the clustering coefficient C_i of node i is defined as the actual edges exist in the k_i neighbors of nodes i divided by the edges while neighbors are fully connected, and $C_{i} = 2 E_{i} / (k_{i} (k_{i} - 1))$ . The clustering coefficient of entire network is defined as: $C = \frac{1}{N} \sum C_{i}$ .

4.3. Algorithm Design

The initial network has m₀ nodes and e₀ edges with the same condition of the BA model. Nodes will be placed in L × L square area, the coordinate of nodes will be decided by p.d.f. The transmission range of the sensor node is R. The algorithm will produce N nodes. At every time step t, perform one of the following phases at random:

With probability p₁, a new sensor node is placed into existing networks, which has m₁ links to the neighbor nodes of existing networks (Fig. 1). The preferential attachment probability

p_{n e i g h b o r} = k_{i} / Γ (t) = k_{i} / \sum_{j} k_{j}

(1)

And the sink node (base station) should broadcast HELLO message to all the nodes. We define three types of messages as follows:

HELLO message

HELLO message can be divided to sink message and node message. The format of sink HELLO message is the following:

Type

(0, 0)

Data

SelectedID

The format of node HELLO message is the following:

Type

(X, Y)

Data

SelectedFlag

AlivedFlag

CONNECT message

The format of node CONNECT message is the following:

Type

(Xs, Ys)

(Xd, Yd)

Data

SelectedFlag

CONFIRM message

The format of node CONFIRM message is the following:

Type

(Xs, Ys)

(Xd, Yd)

Data

SelectedFlag

The type field is specified as 0 to 7, which means sink HELLO message of adding new node, sink HELLO message of adding new links, sink HELLO message of node failure, sink HELLO message of links failure, HELLO message of common node, CONNECT message, and CONFIRM message respectively.

The node whose ID is SelectedID will set the SelectedFlag and AlivedFlag field to 1, and broadcast HELLO message to its neighbor nodes, then select the m₁ nodes, send CONNECT message to the m₁ nodes, and the nodes send CONFIRM message back to the SelectedID node. This is the procedure for establishing the m₁ links.

With probability p₂, m₂ links is added into existing networks (Fig. 2). The sink node randomly selects one node whose ID is SelectedID, the node will select one neighbor node with p_neighbor to establish one connection. This procedure is performed with m₂ times.

With probability p₃, the event of one node failure will happen (Fig. 3). The sink node randomly selects one node whose ID is SelectedID. The node will set the SelectedFlag and the AlivedFlag field to 0, and disconnect with its neighbor nodes.

With probability p₄, the event of m₃ links failure will happen (Fig. 4). The sink node randomly selects one node whose ID is SelectedID, the node will disconnect with its neighbor nodes. This procedure is performed with m₃ times.

Figure 1.

Adding new node with probability p₁.

Figure 2.

Adding new links with probability p₂.

Figure 3.

Node failure with probability p₃.

Figure 4.

Links failure with probability p₄.

The flowchart of the algorithm is the following:

5. Results and Analysis

In order to verify the validity of this model, we conduct the theoretic analysis, and then develop MATLAB toolbox for simulation, as well as we compare the theoretic analysis and the simulation results.

5.1. Theoretic Analysis

We define some analysis parameters as follows:

At time t, the total number of nodes:

N (t) = (p_{1} - p_{3}) t

(2)

the total degree of nodes:

Γ (t) = \sum_{i} k (i, t) = 2 t (m_{1} p_{1} + m_{2} p_{2} - p_{3} ⟨ k ⟩ - m_{3} p_{4})

(3)

the average degree of nodes:

⟨ k ⟩ = Γ (t) / N (T)

(4)

From evolving rule (1), we can get the dynamic equations of k_i

{(\frac{\partial k_{i}}{\partial t})}_{(1)} = m_{1} p_{1} \frac{k_{i}}{Γ (t)}

(5)

From evolving rule (2) and the similar method in [3], we can get the dynamic equations of k _i

{(\frac{\partial k_{i}}{\partial t})}_{(2)} = m_{2} p_{2} [\frac{1}{N (t)} + (1 - \frac{1}{N (t)}) \frac{k_{i}}{Γ (t)}]

(6)

From evolving rule (3) and the similar method in [11], we can get the dynamic equations of k _i

{(\frac{\partial k_{i}}{\partial t})}_{(3)} = - p_{3} \frac{k_{i}}{N (t)}

(7)

From evolving rule 4 and the similar method in [3], we can get the dynamic equations of k _i

{(\frac{\partial k_{i}}{\partial t})}_{(4)} = - m_{3} p_{4} [\frac{1}{N (t)} + \frac{1}{N (t) - 1} (1 - \frac{k_{i}}{Γ (t)})]

(8)

Table 1

The summary of analysis parameters

Parameter	Meaning
$N (t)$	At time step t, the total number of nodes
$Γ (t)$	At time step t, the total degree of nodes
$< k >$	At time step t, the average degree of nodes
$k_{i}$	The degree of the node which is added into the network at time step i

By combining Eqs. (5–8), the total dynamic equations of k_i is as follows:

\begin{aligned} \frac{\partial k_{i}}{\partial t} = & m_{1} p_{1} \frac{k_{i}}{Γ (t)} + m_{2} p_{2} [\frac{1}{N (t)} + (1 - \frac{1}{N (t)}) \frac{k_{i}}{Γ (t)}] - p_{3} \frac{k_{i}}{N (t)} \\ - m_{3} p_{4} [\frac{1}{N (t)} + \frac{1}{N (t) - 1} (1 - \frac{k_{i}}{Γ (t)})] \\ = m_{1} p_{1} \frac{k_{i}}{\frac{2 (p_{1} - p_{3}) (m_{1} p_{1} + m_{2} p_{2} - m_{3} p_{4})}{p_{1} + p_{3}} t} - p_{3} \frac{k_{i}}{(p_{1} - p_{3}) t} \\ + m_{2} p_{2} [\frac{1}{(p_{1} - p_{3}) t} + (1 - \frac{1}{(p_{1} - p_{3}) t}) \frac{k_{i}}{\frac{2 (p_{1} - p_{3}) (m_{1} p_{1} + m_{2} p_{2} - m_{3} p_{4})}{p_{1} + p_{3}} t}] \\ - m_{3} p_{4} [\frac{1}{(p_{1} - p_{3}) t} + \frac{1}{(p_{1} - p_{3}) t - 1} (1 - \frac{k_{i}}{\frac{2 (p_{1} - p_{3}) (m_{1} p_{1} + m_{2} p_{2} - m_{3} p_{4})}{p_{1} + p_{3}} t})] \\ = \frac{m_{1} p_{1} (p_{1} + p_{3})}{2 (p_{1} - p_{3}) (m_{1} p_{1} + m_{2} p_{2} - m_{3} p_{4})} \frac{k_{i}}{t} - \frac{p_{3}}{(p_{1} - p_{3})} \frac{k_{i}}{t} \\ + \frac{m_{2} p_{2}}{(p_{1} - p_{3})} \frac{1}{t} + \frac{m_{2} p_{2} (p_{1} + p_{3})}{2 (p_{1} - p_{3}) (m_{1} p_{1} + m_{2} p_{2} - m_{3} p_{4})} \frac{k_{i}}{t} \\ - \frac{m_{2} p_{2} (p_{1} + p_{3})}{2 (p_{1} - p_{3})^{2} (m_{1} p_{1} + m_{2} p_{2} - m_{3} p_{4})} \frac{k_{i}}{t^{2}} - \frac{m_{3} p_{4}}{(p_{1} - p_{3})} \frac{1}{t} - \frac{m_{3} p_{4}}{(p_{1} - p_{3}) t - 1} \\ + \frac{m_{3} p_{4} (p_{1} + p_{3})}{2 [(p_{1} - p_{3}) t - 1] (p_{1} - p_{3}) (m_{1} p_{1} + m_{2} p_{2} - m_{3} p_{4})} \frac{k_{i}}{t^{2}} \end{aligned}

(9)

With the condition of t − >∞,

\frac{\partial k_{i}}{\partial t} = [\frac{(p_{1} + p_{3}) (m_{1} p_{1} + m_{2} p_{2})}{2 (p_{1} - p_{3}) (m_{1} p_{1} + m_{2} p_{2} - m_{3} p_{4})} - \frac{p_{3}}{p_{1} - p_{3}}] \frac{k_{i}}{t} + [\frac{m_{2} p_{2} - 2 m_{3} p_{4}}{p_{1} - p_{3}}] \frac{1}{t}

(10)

Similar to [3] and [11], let $β = \frac{(p_{1} + p_{3}) (m_{1} p_{1} + m_{2} p_{2})}{2 (p_{1} - p_{3}) (m_{1} p_{1} + m_{2} p_{2} - m_{3} p_{4})} - \frac{p_{3}}{p_{1} - p_{3}}, α = \frac{m_{2} p_{2} - 2 m_{3} p_{4}}{p_{1} - p_{3}}$

Then

\frac{\partial k_{i}}{\partial t} = β \frac{k_{i}}{t} + α \frac{1}{t}

(11)

Taking into account the initial condition k_i(t_i) = m₁, the solution of Eq. (11) is:

k_{i} (t) = (m + α / β) (t / t_{i})^{β} - α / β

(12)

Assuming that we add the node into the networks at equal time intervals, we obtain the probability density function of time t_i:

P (t_{i}) = \frac{1}{m_{0} + t}

(13)

Therefore,

P (k_{i} (t) < k) = P [t_{i} > {(\frac{m + α / β}{k + α / β})}^{1 / β} t] = 1 - \frac{t}{m_{0} + t} {(\frac{m + α / β}{k + α / β})}^{1 / β}

(14)

Then we get the probability density

P (k) = \frac{\partial P [k (i, t) < k]}{\partial k} = \frac{t}{β (m_{0} + t)} (m + \frac{α}{β})^{1 / β} (k + \frac{α}{β})^{- (1 / β + 1)}

(15)

Over long time steps, the Eq. (15) will lead to stationary solution as follows:

P (k) \sim \frac{1}{β} (m + \frac{α}{β})^{1 / β} (k + \frac{α}{β})^{- γ}

(16)

where γ = 1/β + 1.

In the case of ${\begin{cases} p_{1} + p_{2} + p_{3} + p_{4} = 1 \\ 0 \leq p_{3} < p_{1} \leq 1 \\ m_{3} p_{4} < m_{1} p_{1} + m_{2} p_{2} \end{cases}$ , it is easily proved that $\frac{1}{2} < β < 1, 2 < γ < 3$ , which implies that the degree distribution obeys the power law. Actually, the degree distribution exponent is always between 2 to 3 in real networks [3], and such as in [21], all scale-free graphs have the scaling factor between 2 and 3.4875, which have a giant connected component. The theoretic analysis shows that the evolving mechanism of this model is coincident with real sensor networks.

5.2. Simulation Results

We develop a MATLAB simulation toolbox for verifying the validity of this model. Randomly distributed nodes are placed within a two-dimensional network space which is set to 1000 m × 1000 m. The sink node or base station is placed at (0, 0). The transmission range is respectively set to 20 m, 30 m, 40 m, 50 m, 60 m, 70 m, 80 m, 90 m, 100 m, and 110 m. We start our simulations under four different situations:

$m_{1} = 3, m_{2} = 1, m_{3} = 2, p_{1} = 0.5, p_{2} = 0.1, p_{3} = 0.3, p_{4} = 0.1$ ;

$m_{1} = 3, m_{2} = 1, m_{3} = 2, p_{1} = 0.7, p_{2} = 0.1, p_{3} = 0.1, p_{4} = 0.1$ ;

$m_{1} = 4, m_{2} = 1, m_{3} = 2, p_{1} = 0.5, p_{2} = 0.1, p_{3} = 0.3, p_{4} = 0.1$ ;

$m_{1} = 4, m_{2} = 1, m_{3} = 3, p_{1} = 0.7, p_{2} = 0.1, p_{3} = 0.1, p_{4} = 0.1$ ; the evolving time steps of all simulations are 2 × 10³.

Figure 6 shows the degree distribution of our model, which exhibits a power law, and Fig. 7 shows the exponent of degree distribution with different situations. Note that the degree exponent of simulation is a little different than the predicted value, that is caused by randomly links failure. Figure 8 shows the average degree of our model and especially the probability of nodes failure has an important impact on the results. Figure 9 shows the clustering coefficient of all simulations. Figure 10 shows the average path length, with the same reason of Fig. 8, the average path length is much higher than the theoretical value. Figure 11 shows the diameter of the model. From Figs. 10 and 11, we come to know that the probability of nodes failure can affect the network topology, and the higher the probability is, the more the nodes will fail, then either the path length or the diameter will increase consequently. However, this model is robust with randomly nodes failure and links failure. Based on Figs. 6 to 11, the simulation results are in agreement with our theoretical analysis.

Figure 5.

Flowchart of the algorithm.

Figure 6.

The degree distribution.

Figure 7.

The degree exponent with different situations.

Figure 8.

Average degree with different situations.

Figure 9.

The clustering coefficient.

Figure 10.

The average path length.

Figure 11.

The diameter.

6. Conclusions

In many schemes of topology control, the sensor nodes are evenly placed in the space, and the nodes are not clustered, such as in [20]; on the other hand, the nodes may form the cluster with specific protocol, such as LEACH [22]. Our motivation and potential applications in this article have come from our research of national defense, which need to construct reliable wireless sensor networks. The sensor nodes are densely placed in a hostile region, and even a small part of the nodes are destroyed by hostile staff, the power-law topology will constitute better performance following the above analysis. The similar applications can be found in [1, 15, 19].

In this article, the dynamic evolving topology of wireless sensor networks has been modeled. The following evolving events are introduced into the evolving model: adding new nodes, nodes failure, adding new links, and links failure. We use the continuum theory to predict theoretically the exponent of degree distribution, and the analysis results shows that our model exhibits scale-free properties, and the degree distribution exponent is between 2 to 3 with appropriate parameters. In the situation of randomly node failure and links failure, this model has higher robustness, which provides a reference for constructing reliable topology of Wireless Sensor Networks. In future work, we will focus on improving robustness and introduce weighted networks to further enrich this model.

References

Mika

Masaki

, “The Reliability Performance of Wireless Sensor Networks Configured by Power-Law and Other Forms of Stochastic Node Placement,” IEICE Transactions on Communications, vol. E87-B, no. 9, pp. 2511–2520, 2004.

Faloutsos

, “On power-law relationship of the Internet topology,” Computer Communications Review, vol. 29, pp. 251–262, 1999.

Chen

Fan

, “Modeling the complex Internet topology,” Complex Dynamics Communication Networks, Springer, 2005, pp.213–234.

Albert

Jeong

Barabási

A.-L.

, “The Diameter of World Wide Web,” Nature (London), vol. 401, pp. 130–131, 1999.

Barrat

Barthélemy

Pastor-Satorras

Vespignani

, “The architecture of complex weighted networks,” in Proceedings of the National Academy of Sciences (USA), 2004, vol. 101, no. 11, pp. 3747–3752.

Drossel

McKane

A. J.

, “Modeling Food Webs,” in Handbook of Graphs and Networks: From the Genometo the Internet, edited by Bornholdt

Schuster

H. G.

(Wiley-VCH, Berlin, 2003).

Watts

D. J.

Strogatz

S. H.

, “Collective dynamics of ‘small-world’ networks,” Nature, vol. 393, no. 6684, pp. 440–442, 1998.

Barabási

A. L.

Albert

, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999.

Helmy

, “Small worlds in wireless networks,” IEEE Communications Letters, vol. 7, no. 10, pp. 490–492, 2003.

10.

Jin

Papavassiliou

, “Modeling and analyzing the dynamics of mobile wireless sensor networking infrastructures,” in: Proceedings of Vehicular Technology Conference, 2002, pp. 1550–1554.

11.

Sarshar

Roychowdhury

, “Scale-free and stable structures in complex ad hoc networks,” Phys. Rev. E, vol. 69(026101), 2004.

12.

Saffre

Jovanovic

Hoile

Nicolas

, “Scale-free topology for pervasive networks,” BT Technology Journal, vol. 22, no. 3, pp. 200–208, 2004.

13.

Qin

Dai

Wang

Fan

, “Scale-free property of complex ad hoc networks with accelerated growth,” Physica A, vol. 376, pp. 679–686, 2007.

14.

Sen

, “Accelerated growth in outgoing links in evolving networks: Deterministic versus stochastic picture,” Phys. Rev. E, vol. 69(046107), 2004.

15.

Wang

Dang

Jin

, “Scale-free topology for large-scale wireless sensor networks,” in 3rd IEEE/IFIP International Conference in Central Asia on Internet, pp.1–5, 2007.

16.

Garbinato

Rochat

Tomassini

, “Impact of scale-free topologies on gossiping in wireless sensor networks,” Technical Report DOP-20070302, University of Lausanne, 2007.

17.

Lijun

Daoxu

Jiannong

, “Evolution of Wireless Sensor Network,” in IEEE Wireless Communications and Networking Conference, pp. 3003–3007, March 2007.

18.

L. X. and C. G. R. “A local-world evolving network model.” Physica A, vol. 328, pp. 274–286, 2003.

19.

Brooks

R. R.

Pillai

Racunas

Rai

, “Mobile network analysis using probabilistic connectivity matrices,” IEEE Transactions on Systems, Man, and Cybernetics-Part C: Applications and Reviews, vol. 37, no. 4, pp. 694–702, July 2007.

20.

Dai

, “On constructing k-connected k-dominating set in wireless ad hoc and sensor networks,” Journal of Parallel and Distributed Computing, vol. 66, no. 7, pp. 947–958. July 2006.

21.

Aiello Chung Lu

“A random graph model for power law graphs,”

Experiment. Math, vol. 10, no. 1, pp. 53–66, 2001.

22.

Heinzelman

W. B.

Chandrakasan

A. P.

Balakrishnan

“An application-specific protocol architecture for wireless micro-sensor networks,”

IEEE Transactions on Wireless Communications, vol. 1, no. 4, pp. 660–670, 2002.

Dynamics of Wireless Sensor Networks

Abstract

Keywords

1. Introduction

2. Related Work and our Contribution

3. BA Scale-Free Model [8]

3.1. Evolving Process

3.1.1. Equivalent Growth

3.1.2. Preferential Attachment

3.2. Analysis of Degree Distribution

4. Power Law Evolving Model by Stochastic Node Placement

4.1. Network Formalization Definition

4.2. Network Parameters

4.3. Algorithm Design

5.1. Theoretic Analysis

References