Sage Journals: Discover world-class research

Abstract

A core factor to consider when designing wireless sensor networks is the reliable and efficient transmission of massive data from source to destination. In practical situations, data transmission is often disrupted by link interference and interruption resulting in the data losses. Link quality prediction is an important approach to solve this problem. By estimating the link quality based on the past knowledge and information, link quality prediction is essential for routing decisions of future data transmission. Traditional link quality prediction algorithms are simply based on the statistical information of the links in the wireless sensor network. By introducing complex network theory and machine learning techniques, we propose a neighborhood-based nonnegative matrix factorization model to predict link quality in wireless sensor networks. Our model learns latent features of the nodes from the information of past data transmissions combing with local neighborhood structures of the underlying network topology and then estimates the link quality depending on the common latent features of the two nodes between the link. Extensive experiments on both real-world networks and simulation networks demonstrate the effectiveness and efficiency of our proposed model.

1. Introduction

Wireless sensor network (WSN) is a special kind of mobile communication network, which exhibits the properties of dynamic network topology, multihop communication, and limited energy [1, 2]. In wireless sensor network, stable links have great significance since many critical applications fundamentally rely on efficient and reliable data transmission from source node to sink node [3, 4]. However, in practical situations, data transmission is often disrupted by link interference and interruption resulting in the data losses [5, 6]. When the link quality deteriorates, data losses are inevitable since the size of internal buffers of intermediate nodes is limited. In the presence of poor link quality, the sender could easily fill up the buffer so that there is no sufficient time and space to transmit all packets reliably. This problem is especially severe for those applications which strongly require real-time data transmission or high-fidelity data transmission [7]. The main reason for this problem is the lack of feedback of link layer information to the upper layer applications and protocols.

Link quality prediction is an important approach to decrease the probability of data losses in wireless sensor network. For most applications in wireless sensor networks [8–10], it is necessary that each node has thorough knowledge about its direct neighbors. This information is collected and provided by neighborhood management protocols. One important criterion used by neighborhood management protocols to determine the importance of a node is the quality of the communication between nodes, which is provided by link quality prediction [11]. By estimating the link quality based on the past knowledge and information, link quality prediction is essential for routing decisions of future data transmission.

However, link quality prediction remains a challenging task due to the dynamic nature of wireless links. Firstly, the correlations between nodes cannot be directly obtained from the network. Secondly, in some situations, network data is quite sparse that the links used for data transmission are only a small proportion of all possible links.

Motivated by the great practical significance, many algorithms for link quality prediction have been proposed recently. The most existing algorithms simply use statistical information of the links to evaluate the link quality. In this paper, we proposed a nonnegative matrix factorization model for predicting link quality in wireless sensor networks, by introducing complex network theory and machine learning techniques. Our model is a supervised learning model. In our model, we associate the probability of a link with a nonnegative strength variable, which is related with the latent features of the nodes between the link. We also consider the influence of the neighborhood structure and make the latent features of each node learnt from the past data transmissions combing with local neighborhood structures of the underlying network topology.

The rest of the paper is organized as follows. In Section 2, we introduce the related background of link quality prediction in wireless sensor networks. Our proposed neighborhood-based nonnegative matrix factorization model for link quality prediction is described in detail in Section 3. The experimental results and discussions are reported in Section 4. Finally, Section 5 gives the conclusion of this paper.

2. Related Work

In recent years, various approaches have been proposed to provide a meaningful metric describing the actual link-quality and then predicting its future behavior. In this section, an overview of popular link quality prediction algorithms is presented at first. Then, we make an introduction of the link prediction theory in complex networks.

2.1. Link Quality Prediction for Wireless Sensor Networks

Basically, the measurements of link quality can be classified into two categories: physical metrics and logical metrics. Physical metrics depend on the radio hardware and evaluate link quality by the signal strength of a received packet. No additional costs are required by physical metrics, since the measurement is performed by the receiver hardware every time, a packet is received. Common physical metrics include the received signal strength indication (RSSI), the link-quality indication (LQI), and signal-to-noise ratio (SNR). On the other hand, logical metrics estimate the link quality by keeping track of message losses. They do not depend on specific hardware so that they are not influenced by the characteristics of hardware. Typical examples of logical metrics are packet success rate (PSR) [12], required number of packets (RNP) [13], and expected transmission count (ETX) [14].

Woo et al. [12] made the first attempt to estimate the link quality by proposing the window mean with exponentially weighted moving average (WMEWMA). This metric computes the average success rate of the link over a time period and smoothens the average with an EWMA. WMEWMA predicts the PSR of the link and has been widely adopted in WSNs. de Couto et al. [14] proposed ETX which uses the number of expected transmissions for a successful packet transmission as the evaluation of link quality. The ETX of a link is calculated using the forward and reverse delivery ratios of the link. The number of received packets within a fixed time period is counted and compared to the number of expected packets that are periodically broadcasted by each node. RNP introduced by Cerpa et al. [13] incorporates the distribution of losses within the time period. This metric is based on their observation fact that a link with consecutive losses should be rated lower than links with discrete losses.

Weyer et al. [15] proposed adaptive link estimator (ALE), which is an EWMA filter of the measurement PSR. Links with different qualities have different weights in the EWMA filter. For good links, ALE uses a higher weight for more stable estimation, while links with a lower quality are estimated in an agile fashion for a faster reaction.

A Kalman Filter Based Link-Quality Estimation was proposed by Senel et al. [16]. A Kalman filter is used to smoothen the RSSI of successfully received packets and the noise floor is subtracted to obtain an estimation of the SNR. The final PSR is derived by applying a hardware specific SNR-PSR mapping for the transceiver. This approach is very complicated and only applicable to the cases in which SNR and PSR are strictly correlated.

Chen et al. [17] proposed a model to predict link interruption and route interruption in wireless sensor networks by the historical link information and channel state obtained by periodic detection. The periodicity of environmental changes is utilized to help predict link interruption.

LISP proposed by Ma et al. [18] is based on the premise that, in order to achieve the best performance, the application layer behavior should be aware of the link layer conditions and adjust its behavior accordingly. They used the state space model to predict link quality and then provided these estimates as a system level service to application developers.

Wang et al. [19] introduced the supervised learning techniques to predict link quality in wireless sensor network. In their approach, link quality prediction is modeled as a classification problem with the features of the link, including forward probability, backward probability, channel load, and node depth from the source node.

2.2. Link Prediction for Complex Networks

In complex network theory, the research field of link prediction is very similar to the link quality prediction in wireless sensor network. Link prediction in complex networks focuses on estimating the likelihood of the existence of links in the network rather than the link quality.

Link prediction algorithms can be roughly classified into two classes: unsupervised models and supervised models. In unsupervised models, the probability of the existence of a link is measured by some specific similarity indices between the two nodes. Local similarity indices [20–24] only depend on the information of the neighborhoods, such as the common neighbors. Global similarity indices [25–27] require the entire topological information of the network from the perspectives of paths, random walks, and other properties. The similarity in unsupervised models is predefined and is invariant to the specific structure of the input networks.

On the other hand, supervised models use the supervised learning approaches. They usually propose some patterns of the link behaviors and learn a series of parameters according to the observed links. Some popular approaches are hierarchical structure model (HSM) [28], stochastic block model (SBM) [29], and latent factor model (LFM) [30, 31]. The former two models use the explicit topological properties of the network, while latent factor models depend on latent features of the network, which can be viewed as an implicit representation of the network topological information. The main drawback of the former two models is the high calculation complexity, which makes them only applicable to small networks. By contrast, the latent factor models can be trained in linear time with the number of observed links.

3. Our Model

In our model, link quality prediction is formally modeled as a supervised learning problem. The information of past data transmissions is the training set of the model. Given a wireless sensor network, let the link between node i and node j be denoted by link $(i, j)$ . When the packet is successfully transmitted through a link $(i, j)$ , we have the label $A_{i j} = 1$ , otherwise, the label $A_{i j} = 0$ . The predicted score of link quality for link $(i, j)$ obtained by our model is indicated by ${\hat{A}}_{i j}$ . Our model is learnt from the training set by minimizing the errors between the practical labels and the predicted scores. The final goal is to use the model to predict the link quality or successful transmission probability of all the possible links in the network.

3.1. Basic Latent Factor Model

In basic latent factor model (LFM), each node i is associated with a latent feature vector $F_{i} \in R^{k}$ , where k is the number of latent features. The latent features of all the nodes in the network constitute the latent feature matrix $F \in R^{n \times k}$ , where n is the number of nodes in the network. Under the assumption that the link quality between two nodes is higher if they have more similar latent features, the predicted score of the link quality between node i and j can be written as

\begin{matrix} {\hat{A}}_{i j} = L (\sum_{f = 1}^{k} ‍ F_{i f} F_{j f}) = L (F_{i} F_{j}^{T}), \end{matrix}

(1) where

L (\cdot)

is a link function, which is monotonically increasing and is usually taken as identity function or sigmoid function.

The latent features of each node can be learnt by solving the following optimization problem:

\begin{matrix} \min_{F} \sum_{(i, j) \in O} ‍ C (A_{i j}, L (F_{i} F_{j}^{T})) + Ω (F), \end{matrix}

(2) where O is the set of the past successful and unsuccessful transmissions through the links in the network,

C (\cdot)

is a loss function, and

Ω (\cdot)

is a regularization term that prevents overfitting. As suggested in [32], regularized square error loss function and

L_{2}

norm regulation are especially suitable for latent factor models in practical applications. Then, the optimization problem can be rewritten as follows:

\begin{matrix} \min_{F} \sum_{(i, j) \in O} ‍ {(A_{i j} - L (F_{i} F_{j}^{T}))}^{2} + λ ({‖F‖}_{F}^{2}), \end{matrix}

(3) where λ is the regulation parameter and

{‖F‖}_{F}^{2}

is the Frobenius norm of matrix F.

Stochastic gradient descent method is usually used to solve this optimization problem. The total training process exhibits linear time with the number of transmissions in the training set.

3.2. Neighborhood-Based Nonnegative Matrix Factorization Model

In basic latent factor model, the latent features of some nodes may have negative values, which may mislead the whole approach. Moreover, the influences of the neighborhood structure in the network are not considered in basic latent factor model.

We first assume that the latent feature matrix F is a nonnegative matrix and each pair of nodes in the network has a latent interaction of nonnegative strength variable $X_{i j}$ . The transmission between the two nodes can be successful only if the corresponding strength variable $X_{i j} > 0$ . Consider that nodes i and j generate an interaction of strength $X_{i j}^{(f)}$ with each latent feature f using a Poisson distribution with mean $F_{i f} \cdot F_{j f}$ :

\begin{matrix} X_{i j}^{(f)} ~ Pois (F_{i f} \cdot F_{j f}) . \end{matrix}

(4) The strength

X_{i j}

between nodes i and j is the sum of

X_{i j}^{(f)}

for all the latent features:

\begin{matrix} X_{i j} = \sum_{f = 1}^{k} ‍ X_{i j}^{(f)} ~ Pois (\sum_{f = 1}^{k} ‍ F_{i f} \cdot F_{j f}) = Pois (F_{i} F_{j}^{T}) . \end{matrix}

(5) Then, the link quality between the pair of nodes

(i, j)

can be figured out:

\begin{matrix} P (X_{i j} > 0) = 1 - P (X_{i j} = 0) = 1 - \exp (- F_{i} F_{j}^{T}) . \end{matrix}

(6) It is expected that the nodes with larger values in the same latent features have a higher-quality link between them.

Let latent feature matrix F be nonnegative and $1 - \exp (\cdot)$ be the link function we can reformulate the optimization problem (3) as

\begin{matrix} \min_{F > 0} \sum_{(i, j) \in O} ‍ {(A_{i j} - 1 + \exp (- F_{i} F_{j}^{T}))}^{2} + λ ({‖F‖}_{F}^{2}) . \end{matrix}

(7) Taking the node-specific biases into account, the optimization is then

\begin{array}{l} \min_{F, b > 0} \sum_{(i, j) \in O} ‍ {(A_{i j} - 1 + \exp (b_{i} + b_{j} - F_{i} F_{j}^{T}))}^{2} \\ + λ ({‖b‖}_{2}^{2} + {‖F‖}_{F}^{2}), \end{array}

(8) where b is the node-specific bias vector, which is similar to the intercept terms in standard supervised learning.

Now, let us consider the influence of the neighborhoods on the link probability between the nodes. In unsupervised models, several link metrics are defined in the following form:

\begin{matrix} s_{i j} = \sum_{u \in Γ (i) \cap Γ (j)} ‍ w_{u}, \end{matrix}

(9) where

Γ (i)

is the set of neighbors of node i and

w_{u}

is a measurement of the topological properties of node u. Common Neighbors Index (CN) [20] directly counts the neighborhood overlap of the two nodes so that

w_{u} = 1

. For Adamic-Adar Index (AA) [23] and Resource Allocation Index (RA) [24],

w_{u}

is related with the node degree

k_{u}

that

w_{u} = 1 / \log (k_{u})

in AA index and

w_{u} = 1 / k_{u}

in RA index. Here, we extend this form by making each node have different influences upon the links:

\begin{matrix} {\hat{A}}_{i j} = \sum_{u \in Γ (i) \cap Γ (j)} ‍ (w_{u i} + w_{u j}) . \end{matrix}

(10)

In order to reduce the number of parameters, we factorize the matrix $w = X^{T} Y$ , $X, Y \in R^{n \times k}$ . Then, the predicted score of link quality can be reformulated as

\begin{matrix} {\hat{A}}_{i j} = (X_{i} + X_{j}) \sum_{u \in Γ (i) \cap Γ (j)} ‍ Y_{u}^{T} . \end{matrix}

(11)

Finally, we combine the previous two models and predict the link quality by

\begin{array}{l} {\hat{A}}_{i j} \\ = 1 - \exp (b_{i} + b_{j} - α \cdot F_{i} F_{j}^{T} - β \cdot (F_{i} + F_{j}) \sum_{u \in Γ (i) \cap Γ (j)} ‍ Y_{u}^{T}), \end{array}

(12) where α and β are two strength coefficients. Here, we arbitrarily let

X = F

to reduce the number of parameters. Thus, model parameters are learnt by solving the optimization problem associated with

\begin{array}{l} \min_{F, b, Y > 0} \sum_{(i, j) \in O} ‍ (A_{i j} - 1 \\ + \exp (b_{i} + b_{j} - α \cdot F_{i} F_{j}^{T} \\ {- β \cdot (F_{i} + F_{j}) \sum_{u \in Γ (i) \cap Γ (j)} ‍ Y_{u}^{T}))}^{2} \\ + λ ({‖b‖}_{2}^{2} + {‖F‖}_{F}^{2} + {‖Y‖}_{F}^{2}) . \end{array}

(13)

An optimal solution of this optimization problem can be obtained using stochastic gradient descent method. Let the prediction error $A_{i j} - {\hat{A}}_{i j}$ be denoted by $e_{i j}$ . We loop through all observed links in the network. For a given observed transmission through link $(i, j)$ in the training set, we modify the parameters by moving in the opposite direction of the gradient, yielding the following: (i)

$b_{i} \leftarrow \max (0, b_{i} + γ \cdot ((1 - {\hat{A}}_{i j}) \cdot e_{i j} - λ \cdot b_{i}))$ ;

(ii)

$b_{j} \leftarrow \max (0, b_{j} + γ \cdot ((1 - {\hat{A}}_{i j}) \cdot e_{i j} - λ \cdot b_{j}))$ ;

(iii)

$F_{i} \leftarrow \max (0, F_{i} + γ \cdot ((1 - {\hat{A}}_{i j}) \cdot e_{i j} \cdot (α \cdot F_{j} + β \cdot \sum_{u \in Γ (i) \cap Γ (j)} ‍ Y_{u}) - λ \cdot F_{i}))$ ;

(iv)

$F_{j} \leftarrow \max (0, F_{j} + γ \cdot ((1 - {\hat{A}}_{i j}) \cdot e_{i j} \cdot (α \cdot F_{i} + β \cdot \sum_{u \in Γ (i) \cap Γ (j)} ‍ Y_{u}) - λ \cdot F_{j}))$ ;

(v)

$for all u \in Γ (i) \cap Γ (j) : Y_{u} \leftarrow \max (0, Y_{u} + γ \cdot (β \cdot (1 - {\hat{A}}_{i j}) \cdot e_{i j} \cdot (F_{i} + F_{j}) - λ \cdot Y_{u}))$ ,

where γ is the learning rate.

Due to the link function, the predicted score of link quality in our model is in the range $[0, 1]$ , which represents the probability of successful transmission through the link. A link with larger predicted score is more likely to complete a packet transmission in the network. For the links in the training set, the predicted score is approximate to the statistical success probability of past data transmissions. The link quality of the links without any transmission record is predicted according to the transmission information of the neighbor nodes combing with the topology of the underlying network.

4. Experimental Results

4.1. Evaluation on Complex Networks

We first apply our neighborhood-based nonnegative matrix factorization model to several real-world networks, which are widely used in link prediction literature. General information of these real-world networks is shown in Table 1. We also make comparisons with some unsupervised link prediction models, including Common Neighbors Index (CN) [20], Salton Index [22], Preferential Attachment Index (PA) [21], Adamic-Adar Index (AA) [23], and Karz Index [25]. The experiments are implemented by MATLAB 2009b running on a PC with a 3.0 GHz processor and 3 GB memory.

Table 1

General information of the real-world networks.

Network	Description	Node	Present link	Average degree
Karate	Zachary's karate club [35]	34	78	4.58
Dolphin	Social network of Lusseau's dolphins [36]	62	159	5.13
Usair	US air transportation system [37]	332	2126	12.81
Email	E-mail interchanges between members of the University of Rovira i Virgili [38]	1133	5451	9.62
Blog	Hyperlinks between blogs on US politics [39]	1222	16174	27.36
Protein	The interaction between proteins [40]	2473	6269	5.09
Powergrid	The topology of the power grid of the United States [41]	4941	6594	2.67
PGP	The interactions between users of pretty-good-privacy algorithm [42]	10680	24316	4.55

To evaluate the accuracy of different models, we adopt AUC proposed by Hanley and McNeil [33] as the basic measure for the experiments reported in this paper. The AUC value is defined as the probability in which a randomly chosen high-quantity link is assigned with a higher score than a randomly chosen low-quality link. If among n independent comparisons, there are $n_{1}$ times the high-quantity link having a higher score and $n_{2}$ times the scores are equal; the AUC value is

\begin{matrix} AUC = \frac{n_{1} + 0.5 n_{2}}{n} . \end{matrix}

(14) If all the scores are randomly given, the AUC value should be approximated to 0.5. The degree to which the AUC value exceeds 0.5 indicates how much better the model performs than pure chance.

For each network, the present links are partitioned into training set (90%) and test set (10%). The performances of different models on real-world networks are shown in Table 2.

Table 2

The AUC values of different models on real-world networks.

	CN	Salton	PA	AA	Karz	Basic LFM	Our model
Karate	0.7035	0.6387	0.7461	0.7313	0.7877	0.8058	0.8294
Dolphin	0.7786	0.7076	0.6907	0.7851	0.8103	0.8109	0.8275
Usair	0.9368	0.8624	0.9017	0.9461	0.4136	0.9433	0.9598
Email	0.8541	0.8129	0.7814	0.8550	0.6415	0.9131	0.9105
Blog	0.9175	0.8469	0.8977	0.9205	0.4804	0.9292	0.9384
Protein	0.7624	0.6543	0.7232	0.7626	0.6322	0.8849	0.8867
Powergrid	0.5879	0.4411	0.4395	0.5878	0.6587	0.6344	0.6291
PGP	0.8371	0.6805	0.7117	0.8373	0.5245	0.8775	0.8983

As is shown in Table 2, our model performs the best among all the other models on most real-world networks and is only inferior to basic LFM on Email network and Karz Index on Powergrid network. For Karate network, Blog network, and PGP network, our model shows superiority over the unsupervised link prediction models and obvious improvement over basic LFM.

We also find out the reason why the performance of our model is inferior to that of Karz Index on Powergrid network. This is due to the fact that Powergrid network is a highly sparse network in which about 60% of the nodes only have one or two links connecting with other nodes. The sparsity makes many model parameters get insufficient training, which results in the fact that our model does not perform well on this network.

4.2. Simulation on Wireless Sensor Networks

To verify the prediction model, we also make simulations of our model on wireless sensor networks. Here, we use the Matlab as the simulation platform. The channel model is flat Rayleigh fading, carrier frequency is 20 kHz, the modulation is (QAM), and data transmission rate is set to 1000 bits/s. The packet size is set to 1000 bits. The topology of the wireless sensor network is randomly generated by the LFR approach [34]. An example network topology is shown in Figure 1, where the red node denotes the source node and the black node denotes the sink node. The training set contains all the packet transmission records in the wireless sensor network in a period of 1000 seconds. The packet transmission records in the next period of 200 seconds constitute the test set of the experiment.

Figure 1

An example topology of wireless sensor network. The red node denotes the source node and the black node denotes the sink node.

Besides AUC, three other measures, known as precision, recall, and F-score, are also adopted to evaluate the performances of our model. For a given link, we use a threshold to determine whether the coming packet transmission through this link is successful or not. If the predicted link quality exceeds the threshold, the transmission is considered to be successful; otherwise, it is thought that the transmission would fail. Then, there are four possible situations. If the transmission is successful and prediction is success, it is counted as true positive. On the other hand, if the transmission is successful and prediction fails, it is counted as true negative. Similarly, If the transmission failed and prediction is successful, it is counted as false positive. And if the transmission failed and prediction fails, it is counted as false negative. The precision is defined as the ratio of the number of true positives to total number of instances that are predicted to be positive:

\begin{array}{l} precision = (number of ture positives) \\ \cdot (number of ture positives \\ {+ number of negative positives)}^{- 1} . \end{array}

(15)

The recall is defined as the ratio of the number of true positives to total number of instances that are actually positive:

\begin{array}{l} precision = (number of ture positives) \\ \cdot (number of ture positives \\ {+ number of false negatives)}^{- 1} . \end{array}

(16)

F-score is an important measure of the model's accuracy by taking both the precision and recall into account. It can be written in the form of harmonic mean of precision and recall:

\begin{matrix} F = \frac{2 \cdot precision \cdot recall}{precision + recall} . \end{matrix}

(17)

Figure 2 shows the precision, recall, and F-score of our model on wireless sensor networks with the threshold varying from 0 to 1. The two dashed lines are, respectively, the precision curve and recall curve by pure chance. Seen from the curves, the precision and recall of our model are significantly higher than pure chance in most situations. The F-score of our model reaches the highest value of 0.773 when the threshold is equal to 0.3. We also figure out that the AUC of our model is 0.827, which is far larger than 0.5. These measures indicate that our model is effective and promising for link quality prediction in wireless sensor networks.

Figure 2

The precision, recall, and F-score of our model on wireless sensor networks with the threshold varying from 0 to 1.

We also use our model to select the next hop for the data transmission in the network. The neighbor node with larger predicted score has a higher probability to become the next hop of the packet transmission. The improvements of data transmission with our model in a certain period of time are shown in Table 3.

Table 3

The improvements of data transmission with our model.

	Without our model	With our model
Successful transmission number	2289	4230
Failed transmission number	2326	1452
Successful transmission rate	49.60%	74.45%
Packet number received by sink node	19	43

From the above experimental results, we can see that our model is effective for link quality prediction and very suitable for practical applications in wireless sensor networks.

5. Conclusion

In this paper, we propose a neighborhood-based nonnegative matrix factorization model for solving the problem of link quality prediction in wireless sensor networks. We extend link prediction model in complex networks to wireless sensor networks and use the supervised learning techniques to predict the link quality in wireless sensor networks. In our model, the quality of a link is associated with a nonnegative strength variable, which is related with the latent features of the nodes. The influence of the neighborhood structure is also taken into consideration. Thus, the latent features of each node are learnt from the overall topological structure combing with local neighborhood structures of the underlying network. We test our model on several real-world complex networks and also make simulations on wireless sensor networks. The experimental results demonstrate the effectiveness and efficiency of our model for link quality prediction in wireless sensor networks.

Footnotes

Conflict of Interests

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

Acknowledgments

This research work is funded by the National Science Foundation of China (61271316), Shanghai Key Laboratory of Integrated Administration Technologies for Information Security, and Chinese National Engineering Laboratory for Information Content Analysis Technology.

References

Yick

Mukherjee

Ghosal

Wireless sensor network survey

Computer Networks 2008 52 12 2292 2330

10.1016/j.comnet.2008.04.002

2-s2.0-46449122114

Akyildiz

I. F.

Sankarasubramaniam

Cayirci

Wireless sensor networks: a survey

Computer Networks 2002 38 4 393 422

10.1016/s1389-1286(01)00302-4

2-s2.0-0037086890

Gao

Survey on sensor network research

Journal of Computer Research and Development 2008 45 1 1 15

2-s2.0-40049100831

Cerpa

Wong

J. L.

Kuang

Potkonjak

Estrin

Statistical model of lossy links in wireless sensor networks

Proceedings of the 4th International Symposium on Information Processing in Sensor Networks (IPSN ′05)

April 2005

Los Angeles, Calif, USA

IEEE

81 88

10.1109/IPSN.2005.1440900

2-s2.0-33744938433

Akkaya

Younis

A survey on routing protocols for wireless sensor networks

Ad Hoc Networks 2005 3 3 325 349

10.1016/j.adhoc.2003.09.010

2-s2.0-13944283393

Intanagonwiwat

Govindan

Estrin

Directed diffusion: a scalable and robust communication paradigm for sensor networks

Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (MOBICOM ′00)

August 2000

Boston, Mass, USA

ACM

56 67

2-s2.0-0034539015

10.1145/345910.345920

Ren

Liang

Throughput and energy-efficiency-aware protocol for ultra wideband communication in wireless sensor networks: a cross-layer approach

IEEE Transactions on Mobile Computing 2008 7 6 805 815

10.1109/tmc.2007.70765

2-s2.0-42649121951

A survey of sensor network applications

IEEE Communications Magazine 2002 40 8 102 114

Pakzad

S. N.

Fenves

G. L.

Kim

Culler

D. E.

Design and implementation of scalable wireless sensor network for structural monitoring

Journal of Infrastructure Systems 2008 14 1 89 101

10.1061/(asce)1076-0342(2008)14:1(89)

2-s2.0-39549092827

10.

Arora

Dutta

Bapat

Kulathumani

Zhang

Naik

Mittal

Cao

Demirbas

Gouda

Choi

Herman

Kulkarni

Arumugam

Nesterenko

Vora

Miyashita

A line in the sand: a wireless sensor network for target detection, classification, and tracking

Computer Networks 2004 46 5 605 634

10.1016/j.comnet.2004.06.007

2-s2.0-6444240823

11.

Renner

Ernst

Weyer

Turau

Prediction accuracy of link-quality estimators

Wireless Sensor Networks 2011 6567

Berlin, Germany

Springer

1 16 Lecture Notes in Computer Science

10.1007/978-3-642-19186-2_1

12.

Woo

Tong

Culler

Taming the underlying challenges of reliable multihop routing in sensor networks

Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys ′03)

November 2003

14 27

2-s2.0-18844378578

13.

Cerpa

Potkonjak

Wong

J. L.

Estrin

Temporal properties of low power wireless links: Modeling and implications on multi-hop routing

Proceedings of the 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC ′05)

May 2005

414 425

10.1145/1062689.1062741

2-s2.0-29844449933

14.

de Couto

D. S. J.

Aguayo

Bicket

Morris

A high-throughput path metric for multi-hop wireless routing

Wireless Networks 2005 11 4 419 434

10.1007/s11276-005-1766-z

2-s2.0-23044444929

15.

Weyer

Unterschutz

Turau

Connectivity-aware neighborhood management protocol in wireless sensor networks

Proceedings of 7th GI/ITG KuVS Fachgesprach ‘Drahtlose Sensornetze’ (FGSN ′08)

September 2008

23 26

16.

Senel

Chintalapudi

Lal

Keshavarzian

Coyle

E. J.

A Kalman Filter based link quality estimation scheme for wireless sensor networks

Proceedings of the 50th Annual IEEE Global Telecommunications Conference (GLOBECOM ′07)

November 2007

Washington, DC, USA

875 880

10.1109/glocom.2007.169

2-s2.0-39349117692

17.

Chen

Han

Nie

Link prediction and route selection based on channel state detection in UASNs

International Journal of Distributed Sensor Networks 2011 2011 11

939864

10.1155/2011/939864

2-s2.0-81555216656

18.

Djouadi

Cao

LIPS: link prediction as a service for adaptive data aggregation in wireless sensor networks

Proceedings of the 7th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS ′11)

June 2011

1 8

10.1109/dcoss.2011.5982170

2-s2.0-80052507532

19.

Wang

Martonosi

Peh

L.-S.

Predicting link quality using supervised learning in wireless sensor networks

ACM SIGMOBILE Mobile Computing and Communications Review 2007 11 3 71 83

10.1145/1317425.1317434

20.

Newman

M. E. J.

Clustering and preferential attachment in growing networks

Physical Review E: Statistical, Nonlinear, and Soft Matter Physics 2001 64 2

10.1103/PhysRevE.64.025102

2-s2.0-0035420724

21.

Barabási

A.-L.

Albert

Emergence of scaling in random networks

Science 1999 286 5439 509 512

10.1126/science.286.5439.509

2-s2.0-0038483826

22.

Salton

McGill

M. J.

Introduction to Modern Information Retrieval 1983

Auckland, New Zealand

MuGraw-Hill

23.

Adamic

L. A.

Adar

Friends and neighbors on the Web

Social Networks 2003 25 3 211 230

10.1016/s0378-8733(03)00009-1

2-s2.0-10944272139

24.

Zhou

Lü

Zhang

Y.-C.

Predicting missing links via local information

European Physical Journal B 2009 71 4 623 630

10.1140/epjb/e2009-00335-8

2-s2.0-84870843485

25.

Katz

A new status index derived from sociometric analysis

Psychometrika 1953 18 1 39 43

2-s2.0-0002827622

10.1007/BF02289026

26.

Chebotarev

P. Y.

Shamis

E. V.

The matrix-forest theorem and measuring relations in small social groups

Automation and Remote Control 1997 58 9 1505 1514

2-s2.0-0040052015

27.

Liu

Lü

Link prediction based on local random walk

Europhysics Letters 2010 89 5

58007

10.1209/0295-5075/89/58007

28.

Clauset

Moore

Newman

M. E. J.

Hierarchical structure and the prediction of missing links in networks

Nature 2008 453 7191 98 101

10.1038/nature06830

2-s2.0-43049151837

29.

Guimerà

Sales-Pardo

Missing and spurious interactions and the reconstruction of complex networks

Proceedings of the National Academy of Sciences of the United States of America 2009 106 52 22073 22078

10.1073/pnas.0908366106

2-s2.0-76049100050

30.

Menon

Elkan

Link prediction via matrix factorization

Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases, Part II (ECML PKDD ′11)

2011

437 452

31.

Gao

Denoyer

Gallinari

Link prediction via latent factor blockmodel

Proceedings of the 21st Annual Conference on World Wide Web (WWW ′12)

April 2012

New York, NY, USA

ACM

507 508

10.1145/2187980.2188100

2-s2.0-84861028299

32.

Koren

Bell

Volinsky

Matrix factorization techniques for recommender systems

Computer 2009 42 8 30 37

10.1109/mc.2009.263

33.

Hanley

J. A.

McNeil

B. J.

The meaning and use of the area under a receiver operating characteristic (ROC) curve

Radiology 1982 143 1 29 36

10.1148/radiology.143.1.7063747

2-s2.0-0020083498

34.

Lancichinetti

Fortunato

Radicchi

Benchmark graphs for testing community detection algorithms

Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 2008 78 4

046110

10.1103/physreve.78.046110

2-s2.0-55849088356

35.

Zachary

W. W.

An information flow model for conflict and fission in small groups

Journal of Anthropological Research 1997 33 4 452 473

36.

Lusseau

The emergent properties of a dolphin social network

Proceedings of the Royal Society B: Biological Sciences 2003 270 supplement 2 S186 S188

2-s2.0-0242490500

10.1098/rsbl.2003.0057

37.

Batageli

Mrvar

Pajek Datasets, http://vlado.fmf.uni-lj.si/pub/networks/pajek/data/gphs.htm

38.

Guimerà

Danon

Díaz-Guilera

Giralt

Arenas

Self-similar community structure in a network of human interactions

Physical Review E—Statistical, Nonlinear, and Soft Matter Physics 2003 68 6

065103

2-s2.0-1842616539

39.

Adamic

L. A.

Glance

The political blogosphere and the 2004 US Election

Proceedings of the Workshop on the Weblogging Ecosystem (WWW ′05)

August 2005

36 43

40.

Palla

Derényi

Farkas

Vicsek

Uncovering the overlapping community structure of complex networks in nature and society

Nature 2005 435 7043 814 818

10.1038/nature03607

2-s2.0-20444504323

41.

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

42.

Boguñá

Pastor-Satorras

Díaz-Guilera

Arenas

Models of social networks based on social distance attachment

Physical Review E: Statistical, Nonlinear, and Soft Matter Physics 2004 70 5

056122

10.1103/physreve.70.056122

2-s2.0-41349112960

Link Quality Prediction via a Neighborhood-Based Nonnegative Matrix Factorization Model for Wireless Sensor Networks

Abstract

1. Introduction

2. Related Work

2.1. Link Quality Prediction for Wireless Sensor Networks

2.2. Link Prediction for Complex Networks

3. Our Model

3.1. Basic Latent Factor Model

3.2. Neighborhood-Based Nonnegative Matrix Factorization Model

4. Experimental Results

4.1. Evaluation on Complex Networks

4.2. Simulation on Wireless Sensor Networks

5. Conclusion

Footnotes

Conflict of Interests

Acknowledgments

References