Random Walk Based Location Prediction in Wireless Sensor Networks

Abstract

With the development of wireless sensor network (WSN) technologies, WSNs have been applied in many areas. In all WSN technologies, localization is a crucial problem. Traditional localization approaches in WSNs mainly focus on calculating the current location of sensor nodes or mobile objects. In this paper, we study the problem of future location prediction in WSNs. We assume the location histories of mobile objects as a rating matrix and then use a random walk based social recommender algorithm to predict the future locations of mobile objects. Experiments show that the proposed algorithm has better prediction accuracy and can solve the rating matrix sparsity problem more effectively than related works.

1. Introduction

Recently, WSNs have been applied in many areas, such as environmental monitoring [1], target tracking [2], and intrusion detection [3]. However, in all of these areas, location is very important, for data without location in WSNs will be useless. Research of localization is a hot topic in WSN, and it includes two kinds, that is, localization of sensor nodes in the WSN itself and localization of mobile objects using a WSN. For localization of sensor nodes in the WSN itself, several anchor nodes with known location are selected, and locations of other sensor nodes can be calculated with predefined anchor nodes [4]. For localization of mobile objects using a WSN, all sensor nodes are assumed to be anchor nodes, and the location of mobile objects can be calculated with observed anchor nodes [5]. The most popular localization system of this kind is the global position system (GPS).

Given a WSN, where all sensor nodes are anchor nodes, the locations of mobile objects can be calculated with the WSN. Furthermore, if we save all location records of mobile objects, then we can predict future locations of mobile objects with the observed location histories and the WSN. In this paper, we study the problem of future location prediction in WSNs. Here, we assume a WSN as a connected network, where each sensor node has connections with all its neighbors. The reason is that if a mobile object visits location A, it will probably visit A's neighborhood. In a WSN, each node records the number of visits of all mobile objects to itself. Hence, we have a network of sensor nodes and a rating matrix of sensor nodes on all mobile objects. The purpose of this paper is to predict which mobile object will probably visit the desired locations or sensor nodes in the future.

2. Related Works

If we assume each sensor node as a user and each mobile object as an item or a commodity, then the number of visits from a mobile object to a sensor can be assumed to a $|\text{User}|\times |\text{Item}|$ rate matrix and the sensor network becomes a $|\text{User}|\times |\text{User}|$ graph, and thus the location prediction problem can be transformed into a social recommender problem. In this section, we review related works on recommender systems.

2.1. Traditional Recommender Systems

As mentioned by Huang et al. [6], collaborative filtering (CF) method is one of the most commonly used and successfully deployed methods in recommender systems. The CF recommender method can be classified into memory based and model based [3, 4].

The memory-based CF method is heuristic, and it aims to find a neighborhood of similar users [7, 8] or items [9–11] for recommendation. The user-based method predicts ratings based on ratings of neighborhood users, and the item-based method predicts ratings based on ratings of neighborhood items. Here, the similarity between users or items could be Pearson correlation coefficient [12], vector space similarity [13], cosine similarity [14], and so on.

In model-based CF method, one can build a model by the priori $|\text{User}|\times |\text{Item}|$ matrix and predict unknown User-Item ratings with the model [15, 16]. The clustering models divide the matrix into several smaller clusters and use a neighborhood cluster to predict unknown user-item ratings [17, 18]. If the user-item ratings belong to different categories, then classification models can be applied [19]. Here, the priori $|\text{User}|\times |\text{Item}|$ matrix, where each element belongs to a category, is assumed to be training data. With the training data, classification model can be used to predict unknown ratings.

Recently, due to its efficiency in dealing with large datasets, several matrix factorization methods [20–24] have been proposed. The matrix factorization methods factor the $|\text{User}|\times |\text{Item}|$ matrix into two or three low-rank matrixes and employ these low-rank matrixes to make further predictions. The purpose of matrix factorization is to minimize the sum-squared errors of all elements in the priori |User|×|Item| matrix. Given a $n\times m$ rating matrix $R_{n\times m}$ , the Singular Value Decomposition (SVD) [20, 21] is to factor the rating matrix $R_{n\times m}$ into three low-rank matrixes, that is, $R_{n\times m}\simeq A_{n\times k}{\mathbf{\lambda }}_{k\times k}{B}_{k\times m}$ , where $k\ll n,m$ . First, one can factor the rating matrix $R_{n\times m}$ , such that $R_{n\times m}=A_{n\times n}{\mathbf{\lambda }}_{n\times m}{B}_{m\times m}$ , where ${\mathbf{\lambda }}_{n\times m}$ is a positive semidefinite diagonal matrix and ${\lambda }_{i\times i}\ge {\lambda }_{j\times j}\ge \mathrm{0}$ for all $\mathrm{0}\le i\le j\le \min (m,n)$ , and then truncate $A_{n\times n}$ , ${\mathbf{\lambda }}_{n\times m}$ , and $B_{m\times m}$ into $A_{n\times k}$ , ${\mathbf{\lambda }}_{k\times k}$ , and $B_{k\times m}$ , respectively, while keeping the k biggest singular values. Another matrix factorization (MF) method [22–24] is factoring the rating matrix $R_{n\times m}$ , such that $R_{n\times m}=U_{n\times k}{V}_{k\times m}$ ( $k\ll n,m$ ).

2.2. Trust-Based Recommender Systems

Traditional recommender systems have been well studied and developed in both academia and industry, but they all assume that users are independent and identically distributed and ignore the relationships between users. However, in practice, recommendations from different users should have different weights. For example, a preference or advice from a close friend should be more trustable than that of a stranger. Based on this idea, many researchers have recently begun to analyze trust-based recommender systems [25–30]. Trust-based recommender systems use both the rating matrix and the network of users to predict unknown ratings.

TidalTrust [25] applies the social network to find neighbors and aggregates their ratings weighted by the trusts between the source user and his neighbor. The searching of neighbors is based on breadth first search, which finds the nearest raters in the social network, and the trust between the source user and a rater is aggregating the trust value between source user's direct neighbors and the rater, weighted by the trust values between the source user and its direct neighbors. MoleTrust [26] is similar to TidalTrust, except that the computation of trust between the source user and a rater is based on direct neighbors of the raters.

Golbeck and Hendler [27] studied how trust information can be mined and integrated into social-rating systems. They defined trust as “trust in a person is a commitment to an action based on a belief that the future actions of that person will lead to a good outcome,” presented two algorithms for inferring trust relationships between individuals that are not directly connected in the network, and proposed a prototype email client—TrustMail, which could filter spam for an email system.

TrustWalker [28] is a combination of item-based CF and trust-based recommendation, and it considers both ratings of similar items by trustable friends and ratings of the exact item by further neighbors in the social network. The random walk model of TrustWalker is as follows. Starting from the source user u, at step k and at node v, if v has rated i, then it returns to the rating $r_{v,i}$ ; with the probability ${\mathrm{\Phi }}_{v,i,k}$ , the random walk stops, randomly chooses an item j rated by v, and returns to $r_{v,j}$ ; and with the probability $1-{\mathrm{\Phi }}_{v,i,k}$ , the random walk goes to a direct neighbor of v. If ${\mathrm{\Phi }}_{v,i,k}=0$ , TrustWalker is a pure trust-based recommender system; if ${\mathrm{\Phi }}_{v,i,k}=\mathrm{1}$ , the random walk never starts, and thus TrustWalker becomes a traditional item-based CF recommender.

The works in [25–28] are all heuristic or memory based. However, model-based recommender methods, such as SocialTrustEnsemble [29] and SocialMF [30], can also be used in social recommender systems. Both SocialTrustEnsemble and SocialMF apply the matrix factorization method, and they factor both the $|\text{User}|\times |\text{User}|$ matrix and the $|\text{User}|\times |\text{Item}|$ matrix into two low-rank matrixes. While choosing the neighborhood users, although they both use direct neighbors of the source user, they have different weighting methods. SocialTrustEnsemble gives different weights to ratings from different neighborhood users, whereas SocialMF assumes that the weight of a rating recursively depends on the neighbor's neighbors.

2.3. Other Types of Recommendation

Besides recommending items for users, the social recommender systems can also recommend users [31–33], communities [34, 35], and tags [36, 37], as well as all kinds of recommendations for a group of users [38–40]. For more details about social recommender systems, readers can refer to [5].

3. SocialSlopeOne Location Prediction Algorithm

3.1. Problem Definition

In this paper, we consider each sensor node as a user, each mobile object as an item, and the number of visits from a mobile object to a sensor as the rating of user (sensor node) on that item (mobile object), and then we have a $|\text{User}|\times |\text{User}|$ graph and a $|\text{User}|\times |\text{Item}|$ rating matrix.

Assuming a WSN with n sensor nodes and m mobile objects, the WSN network $G=(U,E)$ can be represented as an $n\times n$ adjacency matrix $M_G$ ,

$$\begin{array}{cc}& m_{G,ij}=\{\begin{array}{cc}1,\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}(i,j)\in E\hfill \\ 0,\hfill & \text{otherwise},\hfill \end{array}\end{array}$$

(1)

or a transition probability matrix $P_G$ ,

$$\begin{array}{cc}& p_{G,ij}=\frac{m_{G,ij}}{\left|\text{N}{\text{o}}_i\right|},\end{array}$$

(2)

where $\text{N}{\text{o}}_i$ is the set of nodes linked by outgoing edges of node i and $|\text{N}{\text{o}}_i|={\sum }_{j=1}^n{m}_{G,ij}$ is the cardinality.

Moreover, the rating matrix R is $n\times m$ , and

$$\begin{array}{cc}& r_{i,j}=\{\begin{array}{cc}{r}_{i,j},\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}\text{user}\hspace{0.17em}\hspace{0.17em}i\hspace{0.17em}\hspace{0.17em}\text{has}\hspace{0.17em}\hspace{0.17em}\text{rated}\hspace{0.17em}\hspace{0.17em}\text{item}\hspace{0.17em}\hspace{0.17em}j\hfill \\ \text{null},\hfill & \text{otherwise}.\hfill \end{array}\end{array}$$

(3)

If we consider R as an unweighted graph, then the adjacency matrix of R is $M_R$ ,

$$\begin{array}{cc}& m_{R,ij}=\{\begin{array}{cc}1,\hfill & \text{if}\hspace{0.17em}\hspace{0.17em}{r}_{ij}\ne \text{null}\hfill \\ 0,\hfill & \text{otherwise},\hfill \end{array}\end{array}$$

(4)

and the transition probability matrix of R is $P_R$ ,

$$\begin{array}{cc}& p_{R,ij}=\frac{m_{R,ij}}{\left|\text{N}{\text{o}}_i\right|},\end{array}$$

(5)

where $|\text{N}{\text{o}}_i|$ is the same as (2).

Given a WSN with a network G and a rating matrix R, the purpose of the paper is to predict unknown ratings ${\widehat{r}}_{i,j}=f(i,j)$ in R for $r_{i,j}=\text{null}$ , where f is built with G and R. Table 1 lists all notations used in the paper.

Table 1

Notations.

Notation	Description
n	Number of sensor nodes
m	Number of mobile objects
G	WSN graph
$M_G$	Adjacency matrix of G
$P_G$	Transition probability matrix of G
R	Rating matrix
$r_{i,j}$	The rating of user i on item j
${\widehat{r}}_{i,j}$	The predicted rating of user i on item j
$M_R$	Unweighted adjacency matrix of R
$P_R$	Transition probability matrix of R
$\text{N}{\text{o}}_i$	Neighbor nodes of outgoing edges for i in R
$\text{N}{\text{i}}_i$	Neighbor nodes of ingoing edges for i in R
${\pi }_i$	Stable distribution vector starting from i
$s_{i,j}$	Similarity between user nodes i and j by the random walk model

3.2. Overall Recommender System

While predicting an unknown rating of user i on j, our overall recommender system works as follows.

• (1)

It constructs a social-rating graph with the WSN graph and the rating matrix. Here, we merge the common nodes of users in the two graphs. Figure 1 is an example of a social-rating graph, and Table 2 is its rating matrix, where $u_i$ ( $\mathrm{1}\le i\le \mathrm{7}$ ) are users and $i_i$ ( $\mathrm{1}\le i\le \mathrm{5}$ ) are items.

(2)

While predicting the rating ${\widehat{r}}_{i,j}$ of user i on j, we compute the random walk based similarity, defined in Section 3.3, between user i and the other users.

(3)

Once we get the similarities between i and other users, we can weigh the ratings of each user based on its similarity to i. With the rating matrix, we design a social slope one algorithm to predict the rating ${\widehat{r}}_{i,j}$ , and this is described in Section 3.4.

Table 2

The rating matrix.

Users	Items
	$i_{\mathrm{1}}$	$i_{\mathrm{2}}$	$i_{\mathrm{3}}$	$i_{\mathrm{4}}$	$i_{\mathrm{5}}$
$u_{\mathrm{1}}$	2				?
$u_{\mathrm{2}}$		4	3	5
$u_{\mathrm{3}}$			4		5
$u_{\mathrm{4}}$		5
$u_{\mathrm{5}}$		5	3	4
$u_6$				?
$u_{\mathrm{7}}$		4	?		4

Figure 1

An example of social-rating graph.

3.3. Random Walk Based Similarity

While predicting the rating ${\widehat{r}}_{i,j}$ of user i on j, we can compute the similarities between user i and all other users, that is, $U-\{i\}$ , with a random walk with restart model. The main idea of the model is as follows:

• (i)

starting from the source node i;

(ii)

at each step k and at user node u:

• (a)

with probability ε, return to i;

(b)

with probability $\mathrm{1}-\epsilon$ , continue the random walk:

• (1)

firstly, randomly walk to a direct neighbor user $u^{\prime }$ of u in G;

(2)

secondly, randomly walk to a direct neighbor item i of $u^{\prime }$ in R;

(3)

thirdly, randomly walk to a direct neighbor user $u^{\prime \prime }$ of i in R.

The fingerprint of a random walk is a chain of nodes, which is $〈\text{user},\underset{\mathrm{1}}{\underbrace{〈\text{user},\text{item},\text{user}〉}},\underset{\mathrm{2}}{\underbrace{〈\text{user},\text{item},\text{user}〉}},\dots ,\underset{k}{\underbrace{〈\text{user},\text{item},\text{user}〉}}〉$ . After the kth steps, the random walk would stop at a user node. For example, $〈u_{\mathrm{1}},〈u_{\mathrm{3}},i_{\mathrm{3}},u_{\mathrm{5}}〉,〈u_{\mathrm{4}},i_{\mathrm{2}},u_{\mathrm{2}}〉〉$ is a fingerprint on Figure 1 with $k=\mathrm{2}$ . We use the stable distributions, which are the probabilities of stopping at all user nodes, to represent the similarities between the source user i and others and call them random walk based similarities. For a source user i, the random walk based similarity vector ${\pi }_i$ is

$$\begin{array}{cc}& {\pi }_i=\left(\mathrm{1}-\epsilon \right)P_R{P}_R^T{P}_G^T{\pi }_i+\epsilon {\delta }_i,\end{array}$$

(6)

where the superscript T is the transpose of a matrix, and ${\delta }_i$ is a personalized vector defined as follows:

$$\begin{array}{cc}& {\delta }_i\left(j\right)=\{\begin{array}{cc}1,\hfill & i=j\hfill \\ 0,\hfill & i\ne j.\hfill \end{array}\end{array}$$

(7)

3.4. The Social Slope One Algorithm

As the slope one algorithm is an effective CF algorithm in recommender systems, we apply the idea of slope one for predicting unknown ratings. The slope one algorithm tries to find slope one suggestions in the rating matrix and uses slope one to predict unknown ratings. However, in a social recommender system, the rating matrix is sparse, and the slope one algorithm cannot predict ratings for users who do not have any slope one suggestion.

In order to solve the sparsity of the rating matrix, we propose a social slope one algorithm. While predicting a rating for user u on i, our proposed algorithm works as follows.

3.4.1. Predicting Ratings for New Users

In social recommender systems, a new user is a person that has not rated any item yet, that is, $\text{N}{\text{o}}_u=Ø$ . In this situation, we can take suggestions for the specified item from other users. However, the suggestions from different users should have different weights. Here, we use the average of ratings, which other users have rated for the specified item, weighted by their similarities to the active user,

$$\begin{array}{cc}& {\widehat{r}}_{u,i}={\displaystyle \sum }_{v\in \text{N}{\text{i}}_i}{s}_{u,v}·r_{v,i},\end{array}$$

(8)

where $s_{u,v}$ is the normalized similarity between u and v,

$$\begin{array}{cc}& s_{u,v}=\frac{{\pi }_u\left(v\right)}{{{\displaystyle \sum }}_{w\in \text{N}{\text{i}}_i}{\pi }_u\left(w\right)}.\end{array}$$

(9)

Taking Table 2, for example, $u_{\mathrm{6}}$ is a new user and ${\widehat{r}}_{\mathrm{6,4}}$ is the average of $r_{\mathrm{2,4}}$ and $r_{\mathrm{5,4}}$ weighted by $s_{\mathrm{6,2}}$ and $s_{\mathrm{6,5}}$ , respectively, that is, ${\widehat{r}}_{\mathrm{6,4}}=s_{\mathrm{6,2}}·r_{\mathrm{2,4}}+s_{\mathrm{6,5}}·r_{\mathrm{5,4}}$ .

3.4.2. Predicting Ratings for Non-Cold-Start Users

While predicting the rating ${\widehat{r}}_{u,i}$ of user u on i, if user u is not a new user and the item i is not a new item, then we try to construct slope one suggestions from the rating matrix, so that the slope one algorithm can be used to predict unknown ratings.

If all items that u has rated have been rated only by u itself, that is, $\text{N}{\text{i}}_j=\{u\}$ for all $j\in \text{N}{\text{o}}_u$ , then we can treat ${\widehat{r}}_{u,i}$ as a new user problem, and use (8) to predict the rating. Taking user $u_{\mathrm{1}}$ and item $i_{\mathrm{5}}$ in Table 1, for example, $\text{N}{\text{o}}_{\mathrm{1}}=\{i_{\mathrm{1}}\}$ and $\text{N}{\text{i}}_{\mathrm{1}}=\{u_{\mathrm{1}}\}$ , so ${\widehat{r}}_{\mathrm{1,5}}=s_{\mathrm{1,3}}·r_{\mathrm{3,5}}+s_{\mathrm{1,7}}·r_{\mathrm{7,5}}$ .

Otherwise, if $\text{N}{\text{i}}_j\ne \{u\}$ for at least one $j\in \text{N}{\text{o}}_u$ , then we can construct slope one suggestions from the rating matrix, so that the slope one algorithm can be used. For each item $j\in \text{N}{\text{o}}_u$ , which has been rated by others besides the user u, we construct slope one suggestions using $\text{N}{\text{i}}_i$ and $\text{N}{\text{i}}_j$ . While constructing the rating differences between items i and j, at each time, we select one user p from $\text{N}{\text{i}}_i$ and one user q from $\text{N}{\text{i}}_j$ and minimize the following distance metric:

$$\begin{array}{cc}& \text{dis}\left(p,q\right)=\frac{\left|s_{u,p}-s_{u,q}\right|}{s_{u,p}·s_{u,q}}.\end{array}$$

(10)

Equation (10) means that it is better to choose two ratings for items i and j from users similar to each other, and moreover, both of them are similar to the active user. If users p and q are the same user, then $\text{dis}(p,q)=\mathrm{0}$ is the smallest, and thus the slope one suggestion between i and j is $r_{p,i}-r_{p,j}$ and the weight is $(s_{u,p}+s_{u,q})/\mathrm{2}=s_{u,p}$ . If users p and q are not the same user, then the slope one suggestion is $r_{p,i}-r_{q,j}$ , and the weight is $(s_{u,p}+s_{u,q})/\mathrm{2}$ . For $\text{N}{\text{i}}_i$ and $\text{N}{\text{i}}_j$ , we can construct $\min (|\text{N}{\text{i}}_i|,|\text{N}{\text{i}}_j|)$ slope one suggestions and add them together weighted by the normalized distance, so the predicted rating $r_{u,i}^j$ using the slope one algorithm is

$$\begin{array}{cc}& r_{u,i}^j={\displaystyle \sum }_{r=\mathrm{1}}^{\min \left(\right|\text{N}{\text{i}}_i|,|\text{N}{\text{i}}_j\left|\right)}\frac{\text{di}{\text{s}}_r}{{{\displaystyle \sum }}_{s=\mathrm{1}}^{\min \left(\right|\text{N}{\text{i}}_i|,|\text{N}{\text{i}}_j\left|\right)}\text{di}{\text{s}}_s}·\text{dif}{\text{f}}_r+r_{u,j},\end{array}$$

(11)

where the difference $\text{dif}{\text{f}}_r$ and its weight $\text{di}{\text{s}}_r$ ( $\mathrm{1}\le r\le \min (|\text{N}{\text{i}}_i|,|\text{N}{\text{i}}_j|)$ ) are calculated by Algorithm 1.

Algorithm 1: $\text{SocialDiff}(\text{N}{\text{i}}_i,\text{N}{\text{i}}_j)$ .

Input: $\text{N}{\text{i}}_i$ and $\text{N}{\text{i}}_j$

Output: $〈\text{dif}{\text{f}}_r,\text{di}{\text{s}}_r〉$ for $\mathrm{1}\le \mathrm{r}\le \min \left(\left|\text{N}{\text{i}}_{\mathrm{i}}\right|,\left|\text{N}{\text{i}}_{\mathrm{j}}\right|\right)$

(1) For $r=\mathrm{1}$ to $\min \left(\left|\text{N}{\text{i}}_{\mathrm{i}}\right|,\left|\text{N}{\text{i}}_{\mathrm{j}}\right|\right)$ do

(2)  Find $p\in \text{N}{\text{i}}_i,q\in \text{N}{\text{i}}_j$ , such that $\text{min\hspace{0.17em}dis}(p,q)$ ;

(3)   $\text{dif}{\text{f}}_r=r_{p,i}-r_{q,j}$ , $\text{di}{\text{s}}_r=\frac{s_{u,p}+s_{u,q}}{2}$ ;

(4)  Let $\text{N}{\text{i}}_i=\text{N}{\text{i}}_i-\{p\}$ , $\text{N}{\text{i}}_j=\text{N}{\text{i}}_j-\{q\}$ ;

(5) End for;

(6) Return $〈\text{dif}{\text{f}}_{\mathrm{r}},\text{di}{\text{s}}_{\mathrm{r}}〉$ for $\mathrm{1}\le \mathrm{r}\le \min \left(\left|\text{N}{\text{i}}_{\mathrm{i}}\right|,\left|\text{N}{\text{i}}_{\mathrm{j}}\right|\right)$ ;

Then, for all $j\in \text{N}{\text{o}}_u$ such that $\text{N}{\text{i}}_j\ne \{u\}$ , we add the predicted rating $r_{u,i}^j$ together weighted by $\min (|\text{N}{\text{i}}_i|,|\text{N}{\text{i}}_j|)$ , that is, $w_{u,i}^j=\min (|\text{N}{\text{i}}_i|,|\text{N}{\text{i}}_j|)$ , and then ${\widehat{r}}_{u,i}$ can be calculated by the following equation:

$$\begin{array}{cc}& {\widehat{r}}_{u,i}={\displaystyle \sum }_{j\in \text{N}{\text{o}}_u\wedge \text{N}{\text{i}}_j\ne \left\{u\right\}}\frac{w_{u,i}^j}{{{\displaystyle \sum }}_{k\in \text{N}{\text{o}}_u\wedge \text{N}{\text{i}}_k\ne \left\{u\right\}}^{}{w}_{u,i}^j}{r}_{u,i}^j.\end{array}$$

(12)

In Table 2, if we want to predict the rating ${\widehat{r}}_{\mathrm{7,3}}$ , then $\text{N}{\text{o}}_{\mathrm{7}}=\{i_{\mathrm{2}},i_{\mathrm{5}}\}$ , $\text{N}{\text{i}}_{\mathrm{2}}=\{u_{\mathrm{2}},u_{\mathrm{4}},u_{\mathrm{5}},u_{\mathrm{7}}\}$ , and $\text{N}{\text{i}}_{\mathrm{5}}=\{u_{\mathrm{3}},u_{\mathrm{7}}\}$ . If we assume that $s_{\mathrm{7},k}$ ( $\mathrm{1}\le k\le \mathrm{6}$ ) are equal, then $r_{\mathrm{7,3}}^{\mathrm{2}}=\mathrm{4}+((\mathrm{3}-\mathrm{4})+(\mathrm{4}-\mathrm{5})+(\mathrm{3}-\mathrm{5}))/\mathrm{3}=\mathrm{8}/\mathrm{3}$ , $w_{\mathrm{7,3}}^{\mathrm{2}}=\mathrm{3}$ , $r_{\mathrm{7,3}}^{\mathrm{5}}=\mathrm{4}+((\mathrm{4}-\mathrm{5})/\mathrm{1})=\mathrm{3}$ , $w_{\mathrm{7,3}}^{\mathrm{5}}=\mathrm{1}$ , and finally, we can have ${\widehat{r}}_{\mathrm{7,3}}=(\mathrm{3}/(\mathrm{1}+\mathrm{3}))·(\mathrm{8}/\mathrm{3})+(\mathrm{1}/(\mathrm{1}+\mathrm{3}))·\mathrm{3}=\mathrm{2.75}$ .

3.5. Complexity Analysis

In the problem of location prediction, our approach include two steps, that is, computing nodes' similarities with the random walk model and computing recommender results with the social slope one algorithm.

Theorem 1.

The computational complexity of the random walk based similarity, defined by formula (6), is $k(n^{\mathrm{2}}+\mathrm{2}mn)$ , where k is the number of iterations.

Proof.

The computation of formula (6) is the process of iterations, and the number of iterations decides the precision of the results. Here, we assume the number of iterations is k. At each iteration, there are three matrix-vector multiply operations, and their computational complexities are $n\times m$ , $m\times n$ , and $n\times n$ , respectively. So, the computational complexity of formula (6) is $k(n^{\mathrm{2}}+\mathrm{2}mn)$ .

Theorem 2.

The computational complexity of the social slope one algorithm is $(\mathrm{1}/\mathrm{3})·(r/n)·{(r/m)}^{\mathrm{4}}$ , where r is the number of nonnull elements in the rating matrix R.

Proof.

We assume that the rating matrix R contains r nonnull elements, and then each item is rated by about $r/m$ users and each user rates about $r/n$ items. While constructing slope one suggestions from one item, the $\text{SocialDiff}(r/m,r/m)$ algorithm iterates $r/m$ times (in line 1). At each iteration, the algorithm needs $i^{\mathrm{2}}$ ( $\mathrm{1}\le i\le r/m$ ) time (from line 2 to line 4), that is, $(r/m)·((r/m)+\mathrm{1})·(\mathrm{2}(r/m)+\mathrm{1})/\mathrm{6}$ . So, the computational complexity of the social slope one algorithm is $(\mathrm{1}/\mathrm{3})·(r/n)·{(r/m)}^{\mathrm{4}}$ .

From Theorems 1 and 2, we can have the following corollary.

Corollary 3.

The computational complexity of our random walk based social slope one algorithm is $k(n^{\mathrm{2}}+\mathrm{2}mn)+(\mathrm{1}/\mathrm{3})·(r/n)·{(r/m)}^{\mathrm{4}}$ .

4. Experiments

In this section, we perform experiments on two datasets, report the experimental results, and compare the results with existing CF algorithms. As the acquirement of sensor network data is very difficult, we use two social network data instead. However, both of them have similar characteristics with WSN data.

4.1. Datasets

The datasets in our experiments are Epinions [26] and Flixster [30], and both of them contain a social network and a rating matrix. The Flixster dataset is a social network service, where users can rate movies, the relationships between users are bilateral, and the rating values are 10 discrete numbers in the range [0.5, 5] with step size 0.5. The Epinions dataset is also a social network service containing a social network and a rating matrix. However, the relationships in the Epinions dataset are unilateral, and the rating values are integers from 1 to 5. Basic statistics of the two datasets are in Table 3.

Table 3

Statistics of datasets.

Dataset	No. of users	No. of edges	No. of items	No. of ratings	No. of new users
Epinions	49290	487183	139738	664824	7739
Flixster	786936	7058819	48794	8196077	36360

4.2. Metrics

In the experiments, we treat the social network as known data and make 90% of the rating data as the training set and the remaining 10% as the test data. Our evaluation metrics are RMSE (root mean square error), precision, and coverage.

The RMSE of a model prediction with respect to the estimated variable $r_{u,i}$ is defined as the square root of the mean squared error:

$$\begin{array}{cc}& \text{RMSE}=\sqrt{\frac{{{\displaystyle \sum }}_{(u,i)\in R_{\text{test}}}{\left(r_{u,i}-{\widehat{r}}_{u,i}\right)}^{\mathrm{2}}}{\left|R_{\text{test}}\right|}},\end{array}$$

(13)

where $|R_{\text{test}}|$ is the cardinality of test set $R_{\text{test}}$ .

Precision (also called positive predictive value) is the fraction of retrieved instances that are relevant:

$$\begin{array}{cc}& \text{Precision}@k=\frac{\#\text{hit}}{k},\end{array}$$

(14)

where k is the number of the highest rating items that we recommend to the active user and $\#\text{hit}$ is the number of recommended items which are real in the top-k list. In our experiments, we choose $k=\mathrm{5}$ , that is, $\text{Precision}@\mathrm{5}$ .

Coverage is the ratio of successful recommendations in the whole test set:

$$\begin{array}{cc}& \text{Coverage}=\frac{\#\text{success}}{\left|R_{\text{test}}\right|},\end{array}$$

(15)

where $\#\text{success}$ is the number of test data which we can make a recommendation successfully.

4.3. Baseline Algorithms

In our experiments, we compare the predicting results of different algorithms. Following is the description of labels that we use to denote each of these algorithms.

PearsonCF. It is user based CF algorithm with Pearson correlation coefficient as similarity measure [12].

SlopeOneCF. It is the slope one CF algorithm proposed in [16]. However, the algorithm does not take the social network into consideration and cannot deal with sparse matrix effectively.

TrustWalker [28]. This algorithm takes the social network into consideration and considers both ratings of similar items by trustable friends and ratings of the exact item by further distance users.

SocialMF [30]. It is model based matrix factorization algorithm considering both the social network and the rating matrix.

4.4. Results

In this subsection, we present the results of our experiments, first for all users and then for cold start nodes, and finally evaluate the impact of number of neighbors on the results of the proposed SocialSlopeOne algorithm.

4.4.1. Performance on All Users

We evaluate the performances (RMSE, precision, and coverage) of all algorithms on the whole test set, and the results are listed in Table 4. For better illustrating the results, we compare the results in Table 4 with Figures 2 and 3.

Table 4

Experimental results for all users.

Algorithm	RMSE		Precision		Coverage
	Epinions	Flixster	Epinions	Flixster	Epinions	Flixster
PearsonCF	1.235	0.973	0.721	0.797	0.673	0.739
SlopeOneCF	1.203	0.847	0.805	0.836	0.704	0.729
TrustWalker	1.134	0.904	0.853	0.861	0.952	0.692
SocialMF	1.197	0.896	0.826	0.903	0.718	0.736
SocialSlopeOne	1.096	0.838	0.893	0.897	0. 998	0.882

Figure 2

Comparison of RMSE for all nodes.

Figure 3

Comparison of precision and coverage for all nodes.

As shown in Figure 2, for the Flixster dataset, SocialSlopeOne has similar prediction error to SlopeOneCF, and both of them have lower prediction error than other algorithms; for the Epinions dataset, SocialSlopeOne has the lowest prediction error. In Figure 3, for precision, SocialMF is the best in the Flixster dataset, whereas SocialSlopeOne is the best in the Epinions dataset; for coverage, SocialSlopeOne is the best in both datasets. Moreover, SocialSlopeOne is the best for the sum of coverage and precision for all datasets. Hence, we can have that SocialSlopeOne has the best prediction accuracy and coverage in both datasets.

4.4.2. Performance on Cold Start Nodes

We also evaluate the performances (RMSE, precision, and coverage) of all algorithms on cold start nodes, and the result is listed in Table 5. In our experiments, we define cold start nodes as ratings for new items and new users. For better illustrating the results, we compare the results in Table 5 with Figures 4 and 5.

Table 5

Experimental results for clod start nodes.

Algorithm	RMSE		Precision		Coverage
	Epinions	Flixster	Epinions	Flixster	Epinions	Flixster
PearsonCF	1.382	1.239	0.218	0.453	0.369	0.417
SlopeOneCF	null	null	null	null	null	null
TrustWalker	1.218	1.205	0.734	0.793	0.735	0.665
SocialMF	1.289	1.182	0.609	0.729	0.701	0.682
SocialSlopeOne	1.125	1.026	0.807	0.795	0.897	0.793

Figure 4

Comparison of RMSE for cold start nodes.

Figure 5

Comparison of precision and coverage for cold start nodes.

As shown in Figure 4, SocialSlopeOne has the lowest prediction error in both datasets for cold start nodes. In Figure 5, for precision, SocialSlopeOne and TrustWalker have similar precision, and they are better than others; for coverage, SocialSlopeOne is also the best in both datasets. Moreover, SocialSlopeOne is the best for the sum of coverage and precision for all datasets. Hence, we can conclude that SocialSlopeOne has the best prediction accuracy and coverage for cold start nodes in both datasets.

4.4.3. Impact of k on the Results

In the SocialSlopeOne algorithm, we need to construct $\min (|\text{N}{\text{i}}_i|,|\text{N}{\text{i}}_j|)$ slope one suggestions and distances from $\text{N}{\text{i}}_i$ and $\text{N}{\text{i}}_j$ . In large $\text{N}{\text{i}}_i$ and $\text{N}{\text{i}}_j$ , constructing all slope one suggestions will take a long time. However, small number of these suggestions, especially those from the same user, can approximate the results effectively. We set k as the top list with small distances defined in (10) and use the top-k slope one suggestions to approximate the results.

This top-k method cannot be applied in new items, so we observe the RMSE along with k for new users and all nodes. From Figure 6 we can see that, for both all nodes and new users, the RMSEs decrease with the rising of k. For small k, RMSEs decrease quickly, but as the increasing of k, RMSEs decrease slower and slower, which means that we can use small k to approximate the results for large $\text{N}{\text{i}}_i$ and $\text{N}{\text{i}}_j$ while taking suggestions from other users.

Figure 6

RMSE VS neighbors.

5. Conclusions

Traditional localization technologies focus on calculating the location of sensor nodes or mobile objects using WSNs. However, this paper studies the problem of future location prediction for mobile objects in WSNs. In addition to the WSN, we assume the location histories of all mobile objects as a rating matrix and transfer future location prediction problem to a social recommender problem. In social recommender systems, although current recommender algorithms could give recommender results, they have either low prediction accuracy or high computational complexity and cannot deal with sparse data efficiently. In this paper, we propose a random walk based similarity metric to find similar users and use slope one suggestions from similar users to construct recommender results. With our defined similarity metric, we can find more similar users, and this solves the matrix sparsity problem. In addition, we propose the social slope one recommender method, which has higher prediction accuracy and lower computational complexity. Experiments show that the proposed algorithm has better prediction accuracy and can solve the rating matrix sparsity problem more effectively than related works.