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

Authors: Yuxin Zhao; Shenghong Li; Jia Hou
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

## 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.


---

## Body

## 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 Section2, 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.


## 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 nodei 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 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 nodei is associated with a latent feature vector F
i
∈
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
∈
R
n
×
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(1)
A
^
i
j
=
L
∑
f
=
1
k
‍
F
i
f
F
j
f
=
L
F
i
F
j
T
,where L
(
·
) 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:(2)
min
⁡
F
∑
(
i
,
j
)
∈
O
‍
C
A
i
j
,
L
F
i
F
j
T
+
Ω
F
,where O is the set of the past successful and unsuccessful transmissions through the links in the network, C
(
·
) is a loss function, and Ω
(
·
) 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:(3)
min
⁡
F
∑
(
i
,
j
)
∈
O
‍
A
i
j
-
L
F
i
F
j
T
2
+
λ
F
F
2
,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 matrixF 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
·
F
j
f:(4)
X
i
j
(
f
)
~
Pois
F
i
f
·
F
j
f
.The strength X
i
j between nodes i and j is the sum of X
i
j
(
f
) for all the latent features:(5)
X
i
j
=
∑
f
=
1
k
‍
X
i
j
(
f
)
~
Pois
∑
f
=
1
k
‍
F
i
f
·
F
j
f
=
Pois
F
i
F
j
T
.Then, the link quality between the pair of nodes (
i
,
j
) can be figured out:(6)
P
X
i
j
>
0
=
1
-
P
X
i
j
=
0
=
1
-
exp
⁡
-
F
i
F
j
T
.It is expected that the nodes with larger values in the same latent features have a higher-quality link between them.Let latent feature matrixF be nonnegative and 1
-
exp
⁡
(
·
) be the link function we can reformulate the optimization problem (3) as(7)
min
⁡
F
>
0
∑
(
i
,
j
)
∈
O
‍
A
i
j
-
1
+
exp
⁡
-
F
i
F
j
T
2
+
λ
F
F
2
.Taking the node-specific biases into account, the optimization is then(8)
min
⁡
F
,
b
>
0
∑
(
i
,
j
)
∈
O
‍
A
i
j
-
1
+
exp
⁡
b
i
+
b
j
-
F
i
F
j
T
2
min
⁡
F
,
b
>
0
∑
(
i
,
j
)
∈
O
‍
+
λ
b
2
2
+
F
F
2
,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:(9)
s
i
j
=
∑
u
∈
Γ
(
i
)
∩
Γ
(
j
)
‍
w
u
,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:(10)
A
^
i
j
=
∑
u
∈
Γ
i
∩
Γ
j
‍
w
u
i
+
w
u
j
.In order to reduce the number of parameters, we factorize the matrixw
=
X
T
Y, X
,
Y
∈
R
n
×
k. Then, the predicted score of link quality can be reformulated as(11)
A
^
i
j
=
X
i
+
X
j
∑
u
∈
Γ
i
∩
Γ
j
‍
Y
u
T
.Finally, we combine the previous two models and predict the link quality by(12)
A
^
i
j
=
1
-
exp
⁡
b
i
+
b
j
-
α
·
F
i
F
j
T
-
β
·
F
i
+
F
j
∑
u
∈
Γ
i
∩
Γ
j
‍
Y
u
T
,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(13)
min
⁡
F
,
b
,
Y
>
0
∑
(
i
,
j
)
∈
O
‍
A
i
j
-
1
∑
u
∈
Γ
i
∩
Γ
j
‍
sssssssssssssss
+
exp
⁡
b
i
+
b
j
-
α
·
F
i
F
j
T
∑
u
∈
Γ
i
∩
Γ
j
‍
ssssssddddddddsssssssss
-
β
·
F
i
+
F
j
∑
u
∈
Γ
i
∩
Γ
j
‍
Y
u
T
2
min
⁡
F
,
b
,
Y
>
0
+
λ
b
2
2
+
F
F
2
+
Y
F
2
.An optimal solution of this optimization problem can be obtained using stochastic gradient descent method. Let the prediction errorA
i
j
-
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
←
max
⁡
(
0
,
b
i
+
γ
·
(
(
1
-
A
^
i
j
)
·
e
i
j
-
λ
·
b
i
)
);
(ii)
b
j
←
max
⁡
(
0
,
b
j
+
γ
·
(
(
1
-
A
^
i
j
)
·
e
i
j
-
λ
·
b
j
)
);
(iii)
F
i
←
max
⁡
(
0
,
F
i
+
γ
·
(
(
1
-
A
^
i
j
)
·
e
i
j
·
(
α
·
F
j
+
β
·
∑
u
∈
Γ
(
i
)
∩
Γ
(
j
)
‍
Y
u
)
-
λ
·
F
i
)
);
(iv)
F
j
←
max
⁡
(
0
,
F
j
+
γ
·
(
(
1
-
A
^
i
j
)
·
e
i
j
·
(
α
·
F
i
+
β
·
∑
u
∈
Γ
(
i
)
∩
Γ
(
j
)
‍
Y
u
)
-
λ
·
F
j
)
);
(v)
for
all
u
∈
Γ
(
i
)
∩
Γ
(
j
)
:
Y
u
←
max
⁡
(
0
,
Y
u
+
γ
·
(
β
·
(
1
-
A
^
i
j
)
·
e
i
j
·
(
F
i
+
F
j
)
-
λ
·
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.


## 3.1. Basic Latent Factor Model

In basic latent factor model (LFM), each nodei is associated with a latent feature vector F
i
∈
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
∈
R
n
×
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(1)
A
^
i
j
=
L
∑
f
=
1
k
‍
F
i
f
F
j
f
=
L
F
i
F
j
T
,where L
(
·
) 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:(2)
min
⁡
F
∑
(
i
,
j
)
∈
O
‍
C
A
i
j
,
L
F
i
F
j
T
+
Ω
F
,where O is the set of the past successful and unsuccessful transmissions through the links in the network, C
(
·
) is a loss function, and Ω
(
·
) 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:(3)
min
⁡
F
∑
(
i
,
j
)
∈
O
‍
A
i
j
-
L
F
i
F
j
T
2
+
λ
F
F
2
,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 matrixF 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
·
F
j
f:(4)
X
i
j
(
f
)
~
Pois
F
i
f
·
F
j
f
.The strength X
i
j between nodes i and j is the sum of X
i
j
(
f
) for all the latent features:(5)
X
i
j
=
∑
f
=
1
k
‍
X
i
j
(
f
)
~
Pois
∑
f
=
1
k
‍
F
i
f
·
F
j
f
=
Pois
F
i
F
j
T
.Then, the link quality between the pair of nodes (
i
,
j
) can be figured out:(6)
P
X
i
j
>
0
=
1
-
P
X
i
j
=
0
=
1
-
exp
⁡
-
F
i
F
j
T
.It is expected that the nodes with larger values in the same latent features have a higher-quality link between them.Let latent feature matrixF be nonnegative and 1
-
exp
⁡
(
·
) be the link function we can reformulate the optimization problem (3) as(7)
min
⁡
F
>
0
∑
(
i
,
j
)
∈
O
‍
A
i
j
-
1
+
exp
⁡
-
F
i
F
j
T
2
+
λ
F
F
2
.Taking the node-specific biases into account, the optimization is then(8)
min
⁡
F
,
b
>
0
∑
(
i
,
j
)
∈
O
‍
A
i
j
-
1
+
exp
⁡
b
i
+
b
j
-
F
i
F
j
T
2
min
⁡
F
,
b
>
0
∑
(
i
,
j
)
∈
O
‍
+
λ
b
2
2
+
F
F
2
,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:(9)
s
i
j
=
∑
u
∈
Γ
(
i
)
∩
Γ
(
j
)
‍
w
u
,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:(10)
A
^
i
j
=
∑
u
∈
Γ
i
∩
Γ
j
‍
w
u
i
+
w
u
j
.In order to reduce the number of parameters, we factorize the matrixw
=
X
T
Y, X
,
Y
∈
R
n
×
k. Then, the predicted score of link quality can be reformulated as(11)
A
^
i
j
=
X
i
+
X
j
∑
u
∈
Γ
i
∩
Γ
j
‍
Y
u
T
.Finally, we combine the previous two models and predict the link quality by(12)
A
^
i
j
=
1
-
exp
⁡
b
i
+
b
j
-
α
·
F
i
F
j
T
-
β
·
F
i
+
F
j
∑
u
∈
Γ
i
∩
Γ
j
‍
Y
u
T
,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(13)
min
⁡
F
,
b
,
Y
>
0
∑
(
i
,
j
)
∈
O
‍
A
i
j
-
1
∑
u
∈
Γ
i
∩
Γ
j
‍
sssssssssssssss
+
exp
⁡
b
i
+
b
j
-
α
·
F
i
F
j
T
∑
u
∈
Γ
i
∩
Γ
j
‍
ssssssddddddddsssssssss
-
β
·
F
i
+
F
j
∑
u
∈
Γ
i
∩
Γ
j
‍
Y
u
T
2
min
⁡
F
,
b
,
Y
>
0
+
λ
b
2
2
+
F
F
2
+
Y
F
2
.An optimal solution of this optimization problem can be obtained using stochastic gradient descent method. Let the prediction errorA
i
j
-
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
←
max
⁡
(
0
,
b
i
+
γ
·
(
(
1
-
A
^
i
j
)
·
e
i
j
-
λ
·
b
i
)
);
(ii)
b
j
←
max
⁡
(
0
,
b
j
+
γ
·
(
(
1
-
A
^
i
j
)
·
e
i
j
-
λ
·
b
j
)
);
(iii)
F
i
←
max
⁡
(
0
,
F
i
+
γ
·
(
(
1
-
A
^
i
j
)
·
e
i
j
·
(
α
·
F
j
+
β
·
∑
u
∈
Γ
(
i
)
∩
Γ
(
j
)
‍
Y
u
)
-
λ
·
F
i
)
);
(iv)
F
j
←
max
⁡
(
0
,
F
j
+
γ
·
(
(
1
-
A
^
i
j
)
·
e
i
j
·
(
α
·
F
i
+
β
·
∑
u
∈
Γ
(
i
)
∩
Γ
(
j
)
‍
Y
u
)
-
λ
·
F
j
)
);
(v)
for
all
u
∈
Γ
(
i
)
∩
Γ
(
j
)
:
Y
u
←
max
⁡
(
0
,
Y
u
+
γ
·
(
β
·
(
1
-
A
^
i
j
)
·
e
i
j
·
(
F
i
+
F
j
)
-
λ
·
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 Table1. 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.55To 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 (14)
AUC
=
n
1
+
0.5
n
2
n
.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 Table2.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.8983As is shown in Table2, 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, andF-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:(15)
precision
=
number
of
ture
positives
·
number
of
ture
positives
f
f
f
+
number
of
negative
positives
-
1
.The recall is defined as the ratio of the number of true positives to total number of instances that are actually positive:(16)
precision
=
number
of
ture
positives
·
number
of
ture
positives
f
f
f
+
number
of
false
negatives
-
1
.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:(17)
F
=
2
·
precision
·
recall
precision
+
recall
.Figure2 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, andF-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 Table3.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
43From 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.


## 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 Table1. 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.55To 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 (14)
AUC
=
n
1
+
0.5
n
2
n
.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 Table2.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.8983As is shown in Table2, 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, andF-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:(15)
precision
=
number
of
ture
positives
·
number
of
ture
positives
f
f
f
+
number
of
negative
positives
-
1
.The recall is defined as the ratio of the number of true positives to total number of instances that are actually positive:(16)
precision
=
number
of
ture
positives
·
number
of
ture
positives
f
f
f
+
number
of
false
negatives
-
1
.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:(17)
F
=
2
·
precision
·
recall
precision
+
recall
.Figure2 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, andF-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 Table3.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
43From 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.



---

*Source: 828493-2015-10-11.xml*