A Scale-Free Topology Construction Model for Wireless Sensor Networks

Abstract

A local-area and energy-efficient (LAEE) evolution model for wireless sensor networks is proposed. The process of topology evolution is divided into two phases. In the first phase, nodes are distributed randomly in a fixed region. In the second phase, according to the spatial structure of wireless sensor networks, topology evolution starts from a network of very small size which contains the sink, grows with an energy-efficient preferential attachment rule in the new node's local-area, and stops until all nodes are connected into network. Both analysis and simulation results show that the degree distribution of LAEE follows the power law. The comparison shows that this topology construction model has better tolerance against energy depletion or random failure than other nonscale-free WSN topologies.

1. Introduction

Wireless sensor networks (WSNs) are a kind of self-organized distributed wireless networks composed of a large quantity of energy-limited nodes. Topology construction is one of the primary challenges in WSNs for ensuring network connectivity and coverage, increasing the efficiency of media access control protocols and routing protocols, improving the routing efficiency, extending the network lifetimes, and enhancing the robustness of the network [1–5]. The main aim of topology construction is to build a topology to connect network nodes based on a desired topological property. A dense network topology leads to high energy consumption due to overlapped sensing areas and maintenance costs of topology, while a very sparse network topology is vulnerable to network connectivity [6].

The development of complex networks provides new ideas for topology construction of WSNs. Study on complex networks is a newly emerging subject that focuses on the networks which have nontrivial topological features [7, 8]. There are many common characteristics between WSNs and typical complex networks models: networks contain a large number of nodes and have nontrivial topological features and nodes in networks connect to each other through multihop paths [9]. More importantly, typical complex network models, such as the small-world [10, 11] and scale-free [12] network models, show some characteristics which are beneficial in WSNs. Small-world networks present small average path length between pairs of nodes which is beneficial to saving energy in topology construction and routing in WSNs [13]. Scale-free networks have power-law degree distributions and show an excellent robustness against random node damage [14, 15]. A random attack does not significantly affect the scale-free network performance [8, 16]. Therefore, it is significant to consider complex networks topology when optimising the topology in WSNs [17]. However, complex networks are a kind of relational graphs whose nodes make direct contact according to their logical relationships, while WSNs are spatial graphs in which the existence of links depends on the node's positions and radio range [18]. Thus, the complex networks theory cannot be directly used in WSNs. Some efforts have been made to tune wireless networks into heterogeneous networks with small-world [13, 19–22] or scale-free features [9, 23–25].

In this paper, we propose a local-area and energy-efficient (LAEE) evolution model to build a WSN with scale-free topology. In this model, topology construction is divided into two phases. In the first phase, nodes are distributed randomly in a fixed region, and a node gets other node's information in its transmission range (radio range) through HELLO message. In the second phase, topology evolution starts from the sink, grows with preferential attachment rule, and stops until all nodes are added into network. Following conditions are considered when we design the evolution model: (i) links between nodes depend on the positions and transmission range. Therefore, nodes beyond transmission range cannot make direct contact. (ii) Nodes can only get local information as WSNs are distributed networks. (iii) The remaining energy of each node is considered. Nodes with more remaining energy have higher probability to be connected. (iv) In order to avoid excessive energy consumption, upper bound of degree for each node is needed.

The remainder of this paper is organized as follows: Section 2 reviews background and related works on scale-free networks and scale-free based wireless networks. In Section 3, we propose the LAEE evolution model and deduce the theoretical degree distribution. Section 4 shows simulation results based on LAEE evolution model and examines the tolerance of LAEE to random failures. Finally, we conclude in Section 5.

2. Background and Related Work

2.1. Traditional Topology Constructions in WSNs

Unit disk graph (UDG) is the underlying topology model for WSNs which contains all links in transmission range. Assume that all nodes are randomly distributed in region S. Each node is positioned in a particular subarea with independent probability $φ = π r^{2} / S$ , where r is the transmission range. The probability that a subarea has k nodes is given by the binomial distribution, $p (k) = (\begin{smallmatrix} n \\ k \end{smallmatrix}) φ^{k} (1 - φ)^{n - k}$ , where n is the total number of nodes in the network. With the increase of n, this probability becomes the Poisson distribution $p (k) = (n φ)^{k} e^{- n φ} / k!$ . Then the average number of neighbor nodes is close to $n φ - 1$ . However, UDG model has high concentration of connections that might promote excess energy consumption for periodic topology maintenance and route selection process. Therefore this is an inefficient way of topology construction.

Almost all other topology construction methods in WSNs build a reduced topology from UDG [26, 27]. Based on the topology production mechanism, they can be categorized into Flat Networks and Hierarchical Networks with clustering [27].

In Flat Networks, all nodes are considered to perform the same role in topology and functionality. Typical examples include directed relative neighborhood graph (DRNG) [28], k-nearest neighbor (KNN) [29], TopDisc [30], Euclidean minimum spanning tree (EMST) [31], local Euclidean minimum spanning tree (LEMST) [32], Delaunay triangulation graph (DTG) [33], and cone-based topology control algorithm (CBTC) [34].

In KNN, a node sorts all other nodes in its transmission range in Euclidean distance and then links the k-nearest nodes as neighbors in the final topology. It is a scalable and parameter-free in WSNs and very easy to implement. In DRNG, a link connects nodes u and v if and only if there does not exist a third node w that is closer to both u and v in distance. TopDisc discovers topology by sending query messages and describing the node states using three or four color system. It is a greedy approximation method based on minimum dominating set. In EMST or LEMST, each node builds its overall or local minimum spanning tree based on Euclidean distance and only keeps nodes on tree that is one hop away as its neighbors. In DTG, a triangle formed by three nodes u, v, and w belongs to topology if there are no other nodes in the scope of the triangle. CBTC uses an angle α as a key parameter. In every cone of angle α around node u, there is some node that u can reach.

Nodes in Hierarchical Networks with clustering are heterogeneous in functionality as cluster heads or cluster members. LEACH is a typical Hierarchical Network topology model [35] in which the network is clustered and periodic updated. The cluster heads have the responsibility to communicate directly with the sink for the whole cluster members. A node selects itself to be a cluster head with a probability related to factors such as its remaining energy and whether it has served as cluster head in the last r rounds.

The WSNs topology can be indicated as graph $G (V, E)$ , where the sets of V and E are sensor nodes and topological links, respectively. We denote the number of node's links, also the number of its neighbor nodes, as its degree. All these previous topology construction models show highly concentrated degree distribution, which means these models tend to present homogeneous graph property [36, 37].

2.2. Scale-Free Evolution Models

Barabási and Albert provide an evolution model, called BA model, to generate a scale-free network [12]. The BA model is as follows. (1)

Initialization: the network starts from a fully connected network of small size $m_{0}$ and $m_{0} (m_{0} - 1) / 2$ links.

(2)

Growth: a new node is added.

(3)

Preferential attachment: the new node will connect to m ( $m ⩽ m_{0}$ ) existing nodes according to the preferential attachment. In detail, the new node connects to an existing node i according to the probability $Π_{i} = k_{i} / \sum_{j} ‍ k_{j}$ , where $k_{i}$ is the degree (i.e., numbers of topological links) of node i and j is in the set of all existing nodes at this moment.

(4)

Halt: repeat (2) and (3) until all nodes and links are added to the network.

In BA model, the degree distribution follows the power-law distribution $P (k) = k^{- γ}$ , where the scaling exponent is $γ = 3$ . The $\sum_{j} ‍ k_{j}$ is the sum of degrees of all existing nodes at every step; so the preferential attachment mechanism in BA model works on the global network. Therefore, the BA model is a global topology evolution model which is unable to achieve in most large-scale distributed networks.

Many other scale-free models contain growth and referential attachment features as BA models shows [38–40]. One of the main differences between these algorithms is that they have various referential attachment mechanisms that lead to different values of scaling exponent γ in degree distribution and other scale-free properties.

Li and Chen propose a local-world evolution model [38].

Similarly to BA model, the local-world model is also divided into four steps of initialization, growth, preferential attachment, and halt. But differently, in preferential attachment mechanism of local-world evolution model, the new node selects M of all existing nodes randomly, refereed to as the local world of this new node. So the preferential attachment probability for a new node connecting to an existing node i at time step t is

\begin{matrix} Π_{i} = Π^{'} (i \in local-world) \frac{k_{i}}{\sum_{j \in local-world}^{} k_{j}}, \end{matrix}

(1)

where

Π^{'} (i \in local-world) = M / (m_{0} + t)

. The local-world property shows that the local-wold evolution model is a distributed model. But as these M nodes are selected randomly, the spatial relationships between nodes are not considered. Therefore, the local-world evolution model still cannot describe the topology evolving mechanism in wireless networks.

2.3. WSNs Topology Constructions with Scale-Free Theory

In preferential attachment mechanisms of BA, local-world, and many other scale-free models, the new node has the tendency to connect itself to some richer node (such as with larger degree). In WSNs, the concept of richer node can be extended as a node with more resources, such as with larger degree, more remaining energy, or any other resources.

Several methods have been proposed to build WSNs with the scale-free property [9, 24, 25, 41]. These methods take complex network characteristic such as growth, preferential attachment into account, and some of them consider the local-area feature in WSNs.

Zhang provides a model of WSNs based on scale-free network theory [24]. In this model, each node has a saturation value of degree, $k_{\max}$ , to balance energy consumption. The newly generated node has a certain probability $P_{e}$ to be damaged when it is being added to the network. The probability that the new node will be connected to an existing node i as follows:

\begin{matrix} Π_{i} = P (d_{i v} ⩽ r) (1 - P_{e}) \frac{k_{i}}{\sum_{total-network}^{} k_{j} - q k_{\max}}, \end{matrix}

(2)

where

d_{i v}

is the distance between the new node v and the existing node i, r is the transmission range, and q is the number of nodes which already reaches the saturation value of degree

k_{\max}

. In (2),

P (d_{i v} < r)

refers to the ratio of

π r^{2}

to S, where S is the entire WSNs coverage region.

One of the main drawbacks of Zhang's model is the sum of $Π_{i}$ which is much smaller than 1. The scaling exponent is $γ = 1 + 2 S / π r^{2}$ , where S is the entire coverage region and r is the transmission range. Therefore, another problem is that the scaling exponent γ of degree distribution is much greater than 3, which is not rational in real networks.

Wang et al. propose an arbitrary weight based scale-free topology control algorithm (AWSF) [9]. All nodes in the network are coupled with a sequence of random real numbers W with a power-law distribution $ρ (x) = A x^{- θ}$ , where $θ > 1$ and $A = \int_{\min}^{\max} ‍ ρ (x) d x = 1$ . The balance of energy consumption is not considered in this model. Therefore, there is a possibility that a node with low energy is coupled with a large weight w and therefore has a large degree, which exacerbates the imbalance of energy consumption.

Zhu et al. propose an energy-aware evolution model (EAEM) of WSNs [25]. Energy is taken into account in the EAEM model. This algorithm assumes that the probability $Π_{i}$ that a new node connects to the existing node i depends on its degree $k_{i}$ and the remaining energy of that node. A function $f (E)$ is defined to present the relationship between remaining energy and its ability to be linked. $f (E)$ must be an increasing function, as the more energy a node has, the more probability it will be connected to the new node. Therefore the form of $Π_{i}$ is

\begin{matrix} Π_{i} = \frac{f (E_{i}) k_{i}}{\sum_{local-area}^{} f (E_{j}) k_{j}}, \end{matrix}

(3)

where the local-area in the EAEM is the set of nodes locating in the new node's transmission range. The sum of all nodes'

Π_{i}

is less than 1 and the scaling exponent γ of degree distribution is 1, which is not rational in real networks.

3. Local-Area and Energy-Efficient Evolution Model

In this section, we propose our scale-free topology construction model for WSNs.

We assume that nodes are distributed in a given region with static positions. Then connections between them are built to generate a network. Based on this fact, the process of topology construction is divided into two phases: in the first phase, nodes are distributed randomly. We define the set of scattered nodes as the nodes having no access to the network topology yet in the process of evolution, as shown in Figure 1. An arbitrary node, marked as node v, gets all other nodes' information in its transmission range via HELLO message and takes these nodes as its potential neighbor nodes. Then in the second phase, topology evolution starts from sink, grows with the preferential attachment rule, and stops until all nodes are added into the network.

Figure 1

At every time step, add a scattered node into the network with m ( $m < m_{0}$ ) links.

The LAEE evolution model is proposed.

Step 1.

Nodes are distributed randomly in region S. Each node gets its potential neighbor nodes' information in its transmission range through HELLO message. All these nodes are scattered and topology has not been formed at this moment.

Step 2.

(1)

Topology evolution starts from sink with $m_{0}$ nodes (the sink and its $m_{0} - 1$ potential neighbor nodes) and $e_{0}$ random links between them.

(2)

At every time step, add a scattered node into the network. To do that, we find the node which has the most scattered neighbor nodes and mark it as node a. Choose a scattered node randomly in node a's potential neighbors as the new node, denoting as node b. With this strategy, the network expands outward and fills the region S as fast as possible.

(3)

Randomly choose m nodes, which are already in the topology and are node b's potential neighbors, and link them to node b. If the number of node b's potential neighbors is smaller than m, all these nodes will be linked to this new node. Connect node b with node i in these m potential neighbor nodes based on the preferential attachment:

\begin{matrix} Π_{i} = {Π^{'}}_{i} (i \in local-area) \frac{f (E_{i}) k_{i}}{\sum_{local-area}^{} f (E_{j}) k_{j} - q k_{\max}}, \end{matrix}

(4)

where local-area is the set of node b's potential neighbor nodes in its transmission range, and

k_{\max}

is a predefined default upper bound of node's degree, q is the number of nodes which already have the degree of

k_{\max}

, and

f (E)

is the function mentioned in the EAEM model. When a node reaches the degree of

k_{\max}

, no more links can be added to it.

(4)

Repeat (1), (2), and (3) until all nodes are added to the topology.

LAEE generates a reduced topology from UDG. In LAEE, a topology of network grows step by step via adding new nodes and connecting these nodes to network. According to the LAEE modeling algorithm, at every time step, a scattered node is added to network and then connected to the other nodes within its transmission range in network via preferential attachment rule. One of the conditions of selecting a new node as scattered node is that this node is in the transmission range of at least one node in network. Therefore, once an arbitrary node is connected to other nodes in UDG, it will be connected to at least one node via LAEE.

In (4), $Π_{i}^{'} (i \in local-area)$ refers to the set of node i's neighbor nodes in its transmission range at time step $t;$ that is,

\begin{matrix} Π_{i}^{'} (i \in local-area) = \frac{n φ}{(m_{0} + t)}, \end{matrix}

(5)

where n is the number of nodes in network and

φ = π r^{2} / S

is the possibility of two nodes positioned in each other's transmission range. We assume that only few nodes reach the upper bound

k_{\max}

, so

q k_{\max}

could be ignored here. Therefore, in local area we have

\begin{matrix} \sum_{local-area} ‍ f (E_{j}) k_{j} - q k_{\max} \approx \sum_{local-area} ‍ f (E_{j}) k_{j} = \bar{M} \bar{E} 〈 k 〉, \end{matrix}

(6)

where

\bar{M}

is the expected number of nodes in new node's local-area which is equal to

n φ

as the expected number of nodes in transmission range mentioned in UDG model,

\bar{E}

is the expected value of

f (E)

, and

〈 k 〉 = 2 (m t + e_{0}) / (m_{0} + t)

is the average degree of network at time step t, where

m_{0}

and

e_{0}

represent the number of nodes and links at the beginning, respectively. Then we get the varying rate of

k_{i}

\begin{array}{l} \frac{\partial k_{i}}{\partial t} = m Π_{i} \\ = m Π_{i}^{'} (i \in local-area) \\ \times \frac{f (E_{i}) k_{i}}{\sum_{local-area}^{} f (E_{j}) k_{j} - q k_{\max}} \\ = m \frac{n φ}{m_{0} + t} \frac{f (E_{i}) k_{i}}{n φ \bar{E} (2 (m t + e_{0}) / (m_{0} + t))} = \frac{m f (E_{i}) k_{i}}{2 \bar{E} (m t + e_{0})} . \end{array}

(7)

In a very large-scale network,

e_{0}

can be ignored; then we can get

\begin{matrix} \frac{\partial k_{i}}{\partial t} \approx \frac{f (E_{i}) k_{i}}{2 \bar{E} t} . \end{matrix}

(8)

f (E)

is an increasing function, we set

f (E_{i}) k = E

. Then

\begin{matrix} \frac{\partial k_{i}}{\partial t} = \frac{E k_{i}}{2 \bar{E} t} . \end{matrix}

(9)

According to the initial degree of node i at time step $t_{i}$ , $k_{i} (t_{i}) = m$ , we can get

\begin{matrix} k_{i} = m {(\frac{t}{t_{i}})}^{β}, \end{matrix}

(10)

where

β = E / 2 \bar{E}

. The probability that node i's degree is smaller than k is

\begin{matrix} p (k_{i} (t) < k) = 1 - p (t_{i} < t {(\frac{m}{k})}^{1 / β}) = 1 - \frac{t {(m / k)}^{1 / β}}{m_{0} + t} . \end{matrix}

(11)

Then we can obtain the probability density of the degree of a node with energy E as

\begin{array}{l} P (k_{E}) = \frac{\partial p (k_{i} (t) < k)}{\partial k} = \frac{1}{β} m^{1 / β} \frac{t}{m_{0} + t} k^{- (1 + 1 / β)} \\ \approx \frac{1}{β} m^{1 / β} k^{- (1 + 1 / β)} . \end{array}

(12)

In the above equation, $β \in (E_{\min} / 2 \bar{E}, E_{\max} / 2 \bar{E})$ , where $E_{\min}$ and $E_{\max}$ are the bounds of energy E. Therefore, the distribution $P (k_{E})$ has a power-law form with degree exponent $γ = (1 + 1 / β)$ .

In order to get the probability density of degree with remaining energy E, we have

\begin{matrix} P (k) = \int_{E_{\min}}^{E_{\max}} ‍ ρ P (k_{E}) d E = \int_{E_{\min}}^{E_{\max}} ‍ ρ \frac{1}{β} m^{1 / β} k^{- (1 + 1 / β)} d E, \end{matrix}

(13)

where ρ is the distribution of E with the bounds of

E_{\min}

and

E_{\max}

. ρ satisfies the equation

\int_{E_{\min}}^{E_{\max}} ‍ ρ d E = 1

4. Numerical Results

Table 1 presents the parameters used in our simulation. We distribute $n = 1000$ nodes randomly in the square region S and deploy the sink at a corner marked as (0, 0). We select $m_{0} = 10$ nodes and $e_{0} = 10$ links in sink's transmission range as the initial state of our evolution model. Energy in the networks is uniformly distributed. The value of ρ is a constant which can get from the equation $\int_{E_{\min}}^{E_{\max}} ‍ ρ d E = 1$ . Different values of m in LAEE are considered in our simulation.

Table 1

Parameters for simulation.

Parameter	Value	Definition
n	1000	Number of nodes
r	100 m	Transmission range
S	1000 × 1000 m²	Entire coverage region
$m_{0}$	10	Number of nodes in the initial state
$e_{0}$	10	Number of links in the initial state
m	3, 5, and 8	Links added in every time step
$E_{\min}$	0.5 J	Lower bound of energy E
$E_{\max}$	1 J	Upper bound of energy E
$K_{\max}$	30	Upper bound of degree
ρ	$\int_{E_{\min}}^{E_{\max}} ‍ ρ d E = 1$	Uniform distribution of energy E

The simulation and theoretical degree distributions of LAEE are presented in Figure 2. The theoretical degree distribution of LAEE model is close to the degree distribution of BA model, and the simulation result of degree distribution is close to the theoretical value when $k ⩾ m$ . It is noteworthy that the degree values must be large than m in BA model (each node has m links at least), while there are nodes with degrees less than m in LAEE simulation results. This is because in our model a node may have the number of potential neighbors less than m. If this happens, this node's degree may keep in a low value. In other words, it is due to WSNs' spatial structure. Fortunately, only a small proportion of nodes have degrees less than m. The power-law degree distribution is valid for most of nodes.

Figure 2

(Color online) LAEE degree distribution with $m = 3,5, 8$ .

Fault tolerance is a key issue in WSNs. Many real applications do not require all nodes to be connected. It is appropriate to consider relaxing the connectivity requirement [42]. When a fraction of nodes are out of work, the remains may not be connected and the application of entire network may become invalid. Then, it is important to introduce the giant component, which means the largest connected component [43, 44], to measure the fault tolerance of WSNs with the nodes' failure. Two types of data flows exist in WSNs, flows between any pair of nodes and between sink and other nodes. Therefore, two kinds of giant component are considered correspondingly: the normal one which contains the largest number of nodes and the one with the sink. Sometimes these two giant components are the same, whereas sometimes they are not.

We examine how the fault tolerance of WSNs can be improved by LAEE. Nodes are removed randomly to simulate the procedure of energy depletion or random failure. Typical WSNs construction models UDG, KNN, DTG, LEACH + KNN (LEACH for cluster heads election, KNN for topology construction in each cluster), and LEACH + DTG (DTG for topology construction in each cluster) are used for comparison. The degree parameters are shown in Table 2. We can see that their average degrees are close to that of LAEE with $m = 3$ . Close average degrees mean these topologies contain similar number of links. However, due to the scale-free feature, the degree distribution of LAEE is much wider than other construction models. As Figure 3 shows, with the removing of nodes randomly and gradually, the sizes of giant components decrease. UDG provides upper bounds of giant components. The LAEE presents a larger giant components than KNN, DTG, LEACH + KNN, and LEACH + DTG, though it has the minimum number of average degree. Therefore we deem that LAEE, which presents the scale-free feature in degree distribution, has better tolerance against energy depletion or random failure in WSNs.

Table 2

Degrees in topology.

Model	Avg. degree	Min. degree	Max. degree
UDG	29.21	6	53
LAEE ( $m = 3$ )	5.22	1	25
LAEE ( $m = 5$ )	7.88	1	29
LAEE ( $m = 8$ )	11.34	2	29
KNN ( $k = 6$ )	6	6	6
DTG	5.85	3	11
LEACH + KNN ( $k = 6$ )	5.98	4	6
LEACH + DTG	5.64	3	10

Figure 3

(Color online) Giant component size of WSNs under random nodes failure.

5. Conclusions

Topology control is one of the primary challenges to make WSNs resource efficient. In this paper, we propose a local information and energy-efficient based topology evolution model. The process of topology evolution is divided into two phases. In the first phase, nodes are distributed randomly in a fixed region. In the second phase, topology evolution starts from sink, grows with preferential attachment rule, and stops until all nodes are added into network. The theoretical degree distribution of LAEE evolution model is approaching that of BA model. Simulation result shows that when $k ⩾ m$ , the degree distribution follows the power law. The LAEE model has better tolerance against energy depletion or random failure than other nonscale-free WSNs topology with close average degrees.

Footnotes

Conflict of Interests

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

Acknowledgments

This work is supported by the National Natural Science Foundation of China (NSFC61174153) and (NSFC61273072) and the Research Funds for the Ocean Discipline in Zhejiang University (no. 2012HY005A).

References

Abbasi

hafie Bin Abd Latiff

Chizari

An overview of distributed energy-efficient topology control for wireless ad hoc networks

Mathematical Problems in Engineering 2013 2013 16

126269

10.1155/2013/126269

Üster

Lin

Integrated topology control and routing in wireless sensor networks for prolonged network lifetime

Ad Hoc Networks 2011 9 5 835 851

10.1016/j.adhoc.2010.09.010

2-s2.0-79952573678

Akbari Torkestani

An energy-efficient topology construction algorithm for wireless sensor networks

Computer Networks 2013 57 7 1714 1725

10.1016/j.comnet.2013.03.001

2-s2.0-84877581556

Wang

Lang

Wang

Hou

Study on WSN topology division and lifetime

Proceedings of the IEEE International Conference on Computer Science and Automation Engineering (CSAE '11)

June 2011

IEEE

380 384

10.1109/CSAE.2011.5953244

2-s2.0-80051900921

Yang

A survey on topology issues in wireless sensor network

Proceedings of the International Conference on Wireless Networks (ICWN '06)

2006

Las Vegas, Nev, USA

503

Qureshi

H. K.

Rizvi

Saleem

Khayam

S. A.

Rakocevic

Rajarajan

Evaluation and improvement of CDS-based topology control for wireless sensor networks

Wireless Networks 2013 19 1 31 46

10.1007/s11276-012-0449-9

2-s2.0-84871770591

Lü

Chen

Analysis, control and applications of complex networks: a brief overview

Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS '09)

May 2009

1601 1604

10.1109/ISCAS.2009.5118077

2-s2.0-70350181757

Cui

L. Y.

Kumara

Albert

Complex networks: an engineering view

IEEE Circuits and Systems Magazine 2010 10 3 10 25

10.1109/MCAS.2010.937883

2-s2.0-77956281328

Wang

Dang

Jin

Scale-free topology for large-scale wireless sensor networks

Proceedings of the 3rd IEEE/IFIP International Conference in Central Asia on Internet (ICI '07)

September 2007

10.1109/CANET.2007.4401663

2-s2.0-48749093248

10.

Watts

D. J.

Strogatz

S. H.

Collective dynamics of “small-world” networks

Nature 1998 393 6684 440 442

10.1038/30918

2-s2.0-0032482432

11.

Newman

M. E. J.

Watts

D. J.

Renormalization group analysis of the small-world network model

Physics Letters A 1999 263 4–6 341 346

10.1016/S0375-9601(99)00757-4

MR1732095

2-s2.0-0347334779

12.

Barabási

Albert

Emergence of scaling in random networks

Science 1999 286 5439 509 512

10.1126/science.286.5439.509

MR2091634

2-s2.0-0038483826

13.

Guidoni

D. L.

Mini

R. A. F.

Loureiro

A. A. F.

On the design of resilient heterogeneous wireless sensor networks based on small world concepts

Computer Networks 2010 54 8 1266 1281

10.1016/j.comnet.2009.10.021

ZBL1204.68017

2-s2.0-77953256068

14.

Albert

Jeong

Barabási

A.-L.

Error and attack tolerance of complex networks

Nature 2000 406 6794 378 382

10.1038/35019019

2-s2.0-0034721164

15.

Gao

Meng

Research on degree control resistance to frangibility of scale-free networks

Proceedings of the 2nd International Conference on Communication Software and Networks (ICCSN '10)

February 2010

42 45

10.1109/ICCSN.2010.59

2-s2.0-77952370024

16.

Xia

Hill

D. J.

Attack vulnerability of complex communication networks

IEEE Transactions on Circuits and Systems II: Express Briefs 2008 55 1 65 69

10.1109/TCSII.2007.908954

2-s2.0-50249085631

17.

Ishizuka

Aida

The reliability performance of wireless sensor networks configured by power-law and other forms of stochastic node placement

IEICE Transactions on Communications 2004 87 9 2511 2520

2-s2.0-5444257457

18.

Helmy

Small worlds in wireless networks

IEEE Communications Letters 2003 7 10 490 492

10.1109/LCOMM.2003.818887

2-s2.0-0242332739

19.

Chitradurga

Helmy

Analysis of wired short cuts in wireless sensor networks

Proceedings of the IEEE/ACS International Conference on Pervasive Services (ICPS '04)

July 2004

IEEE

167 177

2-s2.0-10444228046

10.1109/PERSER.2004.1356794

20.

Cavalcanti

Agrawal

Kelner

Sadok

Exploiting the small-world effect to increase connectivity in wireless ad hoc networks

Proceedings of the Telecommu-nications and Networking (ICT '04)

2004

Springer

388 393

21.

Verma

C. K.

Tamma

B. R.

Manoj

B. S.

Rao

A realistic small-world model for wireless mesh networks

IEEE Communications Letters 2011 15 4 455 457

10.1109/LCOMM.2011.020111.100266

2-s2.0-79954633147

22.

Lin

Small-world model based topology optimization in wireless sensor network

Proceedings of the International Symposium on Information Science and Engineering (ISISE '08)

December 2008

102 106

10.1109/ISISE.2008.245

2-s2.0-62449278846

23.

Luo

Wang

Energy-aware topology evolution model with link and node deletion in wireless sensor networks

Mathematical Problems in Engineering 2012 2012 12

281465

10.1155/2012/281465

2-s2.0-81555219636

24.

Zhang

Model design of wireless sensor network based on scale-free network theory

Proceedings of the 5th International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM '09)

September 2009

Beijing, China

IEEE Press

3244 3247

10.1109/WICOM.2009.5303044

2-s2.0-73149115316

25.

Zhu

Luo

Peng

Luo

Complex networks-based energy-efficient evolution model for wireless sensor networks

Chaos, Solitons and Fractals 2009 41 4 1828 1835

10.1016/j.chaos.2008.07.032

2-s2.0-67349223908

26.

Wightman

P. M.

Labrador

M. A.

A3Cov: a new topology construction protocol for connected area coverage in WSN

Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC '11)

March 2011

522 527

10.1109/WCNC.2011.5779187

2-s2.0-79959291314

27.

Jardosh

Ranjan

A survey: topology control for wireless sensor networks

Proceedings of the International Conference on Signal Processing Communications and Networking (ICSCN '08)

January 2008

422 427

10.1109/ICSCN.2008.4447231

2-s2.0-48149108943

28.

Hou

J. C.

Topology control in heterogeneous wireless networks: problems and solutions

Proceedings of the 23rd AnnualJoint Conference of the IEEE Computer and Communications Societies (INFOCOM '04)

March 2004

IEEE

232 243

2-s2.0-8344232302

29.

Blough

D. M.

Leoncini

Resta

Santi

The k-neighbors approach to interference bounded and symmetric topology control in ad hoc networks

IEEE Transactions on Mobile Computing 2006 5 9 1267 1282

10.1109/TMC.2006.139

2-s2.0-33746898272

30.

Deb

Bhatnagar

Nath

A topology discovery algorithm for sensor networks with applications to network management, 2002

31.

Agarwal

P. K.

Edelsbrunner

Schwarzkopf

Welzl

Euclidean minimum spanning trees and bichromatic closest pairs

Discrete & Computational Geometry 1991 6 1 407 422

10.1007/BF02574698

2-s2.0-51249179376

32.

Hou

J. C.

Sha

Design and analysis of an MST-based topology control algorithm

Proceedings of the 22nd Annual Joint Conference on the IEEE Computer and Communications Societies

April 2003

1702 1712

2-s2.0-0041973675

33.

X.-Y.

Calinescu

Wan

P.-J.

Wang

Localized delaunay triangulation with application in Ad Hoc wireless networks

IEEE Transactions on Parallel and Distributed Systems 2003 14 10 1035 1047

10.1109/TPDS.2003.1239871

2-s2.0-0242410472

34.

Halpern

J. Y.

Bahl

Wang

Wattenhofer

A cone-based distributed topology-control algorithm for wireless multi-hop networks

IEEE/ACM Transactions on Networking 2005 13 1 147 159

10.1109/TNET.2004.842229

2-s2.0-15544363212

35.

Heinzelman

W. B.

Chandrakasan

A. P.

Balakrishnan

An application-specific protocol architecture for wireless microsensor networks

IEEE Transactions on Wireless Communications 2002 1 4 660 670

10.1109/TWC.2002.804190

2-s2.0-33646589837

36.

Liu

Zuo

Yang

Research on key nodes of wireless sensor network based on complex network theory

Journal of Electronics 2011 28 3 396 401

10.1007/s11767-011-0611-z

2-s2.0-83355168366

37.

Tong

Niu

J. W.

G. Z.

Long

Gao

X. P.

Complex networks properties analysis for mobile ad hoc networks

IET Communications 2012 6 4 370 380

10.1049/iet-com.2010.0651

MR2952206

2-s2.0-84860168033

38.

Chen

A local-world evolving network model

Physica A. Statistical Mechanics and its Applications 2003 328 1-2 274 286

10.1016/S0378-4371(03)00604-6

MR2012478

ZBL1029.90502

2-s2.0-0141860156

39.

Albert

Barabási

A.-L.

Topology of evolving networks: local events and universality

Physical Review Letters 2000 85 24 5234 5237

10.1103/PhysRevLett.85.5234

2-s2.0-0142077573

40.

Chen

Fan

Modelling the complex internet topology

Complex Dynamics in Communication Networks 2005

Springer

213 234

41.

Ganesan

Size of the giant component in a random geometric graph

Proceedings of the IEEE International Conference on Network Protocols

2012

IEEE

81 84

42.

Mao

Anderson

B. D. O.

On the giant component of wireless multihop networks in the presence of shadowing

IEEE Transactions on Vehicular Technology 2009 58 9 5152 5163

10.1109/TVT.2009.2026480

2-s2.0-70450183207

43.

Ganesan

Size of the giant component in a random geometric graph

Annales de l'Institut Henri Poincare B Probability and Statistics 2013 49 4 1130 1140

10.1214/12-AIHP498

MR3127916

44.

Hekmat

Van Mieghem

Connectivity in wireless ad-hoc networks with a log-normal radio model

Mobile Networks and Applications 2006 11 3 351 360

10.1007/s11036-006-5188-7

2-s2.0-33646556427