A Location Prediction Algorithm with Daily Routines in Location-Based Participatory Sensing Systems

Abstract

Mobile node location predication is critical to efficient data acquisition and message forwarding in participatory sensing systems. This paper proposes a social-relationship-based mobile node location prediction algorithm using daily routines (SMLPR). The SMLPR algorithm models application scenarios based on geographic locations and extracts social relationships of mobile nodes from nodes' mobility. After considering the dynamism of users' behavior resulting from their daily routines, the SMLPR algorithm preliminarily predicts node's mobility based on the hidden Markov model in different daily periods of time and then amends the prediction results using location information of other nodes which have strong relationship with the node. Finally, the UCSD WTD dataset are exploited for simulations. Simulation results show that SMLPR acquires higher prediction accuracy than proposals based on the Markov model.

1. Introduction

Participatory sensing is a recent appearing sensing technology which emphasize that people participate in the sensing process. Participatory sensing enables individuals and communities to gather, analyze, and share local knowledge and to subsequently make intelligent decisions and also offer social services. The earliest research of participatory sensing is executed by Srivastava et al. who have proposed the conception of urban sensing in a technical report [1] in the year 2006 to discuss the system architecture and technical methods of urban sensing. The MSG (Mobile Sensing Group) laboratory at Dartmouth College also conducts research on this area, including BikeNet [2], SoundSense [3], CenceMe [4, 5], MetroSense [6], and Bubble-Sensing [7].

Participatory sensing systems rely on mobile phone users to sense and transmit data with diverse purposes in the process of monitoring or solving a particular problem. Based on the large number of users, participatory sensing systems have the potential to acquire large amounts of data from various places and address large-scale location-based problems [8–10]. A typical example of location-based participatory sensing systems collects and records air quality measurements to monitor the pollution of a particular location. What is more, the smartphone with Internet connectivity can also contribute to the participatory sensing systems' growth. In [11], a solution based on web services is proposed to permit the interaction between a mobile application and the IPv6 compliant WSNs scenario.

In participatory sensing systems, mobile devices are usually weakly connected. Due to uncertainty of connection, nodes sometimes need encounter opportunities to accomplish data communication and transmission. If the location of mobile nodes can be predicted ahead of several time slots, the service quality and efficiency of the system will be remarkably improved.

In order to solve the location prediction problems, human mobility has been analyzed at different geographic scales [12–14]. In [12] the limits of predictability provided by humans' mobility patterns are examined. The data that is collected by 50,000 anonymous mobile phone users over a period of three months has been used to study the humans' mobility patterns, and different entropy measures are adopted in this research to estimate the potential predictability in human dynamics. Based on their analysis, a 93% potential predictability in user mobility across the whole user base is found in their report. In [13] the location data from 100,000 mobile phone users collected by tracking each person's position for six months is investigated. This research shows that individual mobility patterns of the test persons can be described by a single spatial probability distribution after some corrective preprocessing. Thus the results of this study suggest that humans generally follow simple reproducible patterns.

Based on the human mobility analysis, different techniques based on the Markov model have been applied to location prediction problems of human individuals. In [15], a set of discrete locations has been defined using the WIFI cells on a university campus. Two different kinds of location predictors, the kth order Markov predictor as well as a LZ-based predictor, are tested in predictions to the next location. Based on the test results, the research shows that the second order Markov predictor with a certain fallback feature performs best and provided a median accuracy of 72%. Literature [16] presents a similar extended Markov predictor, which takes the arrival time and residence time into account. Specifically, delay embedding is used to extract location sequences of a certain length from time series. Then these sequences are directly used to predict a user's location, and the prediction result is obtained by comparing the last observed locations to all embedded location sequences.

Meanwhile, hidden Markov models (HMMs) are also considered to predict human mobility. Literature [17] presents a hybrid method on the basis of hidden Markov models. The proposed approach clusters location histories according to their characteristics, and the latter trains an HMM for each cluster. Based on HMMs, location characteristics are considered as unobservable parameters and the effects of each individual's previous actions are also accounted in the process of predictions. Finally, a prediction accuracy of 13.85% can be achieved when considering regions of roughly 1280 square meters.

Except for the Markov model and HMM, there are some other location prediction algorithms that are used to analyze location information in literature [18–26], such as the artificial neural network-based algorithm [18], Bayesian network-based methods [19, 20], mobile-sink-based methods [21, 22], the regression-based method [23], and mobile anchor assisted localization algorithms [24, 25]. These methods predict future positions of nodes from different perspectives, which focus on the behavior of each single node.

However, in fact the behavior of a node is decided not only by location state of the former period but also by the social relationship of mobile users.

In this paper, a social-relationship-based mobile node location prediction algorithm using daily routines (SMLPR) is proposed. In this approach, the social relationship of nodes is used to optimize the location prediction algorithm so that it can better adapt to participatory sensing applications and promote the prediction accuracy. The remainder of this paper is organized as follows: the network model is illustrated in Section 2. Section 3 specifies the mobile node location prediction algorithm. Extensive simulations have been done for performance evaluation in Section 4. Section 5 concludes the paper.

2. Network Model

Human movements often exhibit a high degree of repetition including regular visits to certain places and regular contacts during daily activities. In this paper, a hybrid urban network model is proposed for participatory sensing systems, as illustrated in Figure 1. The map M is partitioned into small regions. In other words, M is represented as a finite set of regions $\{a_{\mathrm{1}},\dots ,a_n\}$ such that ${\bigcup }_{i=\mathrm{1}}^n{a}_i=M$ with $a_i\bigcap a_j=\varnothing$ ( $i\ne j$ ). The movement possibility of the user from one region to another is represented by a directed graph. In these regions, the sensed data needs to be aggregated to reduce network overhead and to enhance its usefulness among consumers.

Figure 1

Participatory sensing scenario.

As mentioned above, the network has been reinforced as a mixture of an opportunistic network and a centralized infrastructure which is shown in Figure 1. The centralized infrastructure consists of a number of wireless access points (APs) and a backbone connecting the APs. The purpose of this model is to collect data from a peer-to-peer network (scenario 2 in Figure 1) or WIFI APs which is in the vicinity of the consumers (scenarios 1 and 3 in Figure 1), rather than collecting it from any 3G/4G server. Mobile nodes that are carrying smart device can only access to the network when they are walking into the transmission range of any AP, and data transmission can only occur between peer counterparts when they fall into each other's transmission range as in normal opportunistic networks.

Definition 1 (location).

Inside a geographical region, a mobile device closest to a fixed location is selected to perform data collection and the collected data is sent to a set of bounding APs where it is stored and pulled by the consumers. The fixed location is termed as the aggregation location.

Definition 2 (location granularity).

An aggregation location includes a set of APs in adjacent position. The granularity of the location represents the location's transmission range which is decided by the number and the scope of the APs in the same geographical region.

In this study, historical trajectories of users connecting with APs are recorded and they are divided by time granularity. Trajectory of a moving user is defined as a sequence of points $\{({\mathrm{i}\mathrm{d}}^j,l_{\mathrm{1}},v{t}_{\mathrm{1}}),({\mathrm{i}\mathrm{d}}^j,l_{\mathrm{2}},v{t}_{\mathrm{2}}),\dots ,({\mathrm{i}\mathrm{d}}^j,l_m,v{t}_m)\}$ , where ${\mathrm{i}\mathrm{d}}^j$ is the user's identifier and location $l_{\mathrm{1}}$ is represented by a set of adjacent APs which users are connecting to at time slot $v{t}_i$ , $\mathrm{1}\le i\le m$ . In this paper, a mechanism to construct aggregation location based on the information of APs is proposed, which divides APs into different locations in different granularities.

The urban scenario is transformed into a graph $G=\{E,V,W\}$ , where each AP is replaced by a vertex $v\in V$ and the relation between two APs is replaced by an edge $e\in E$ , where $E\subset V\times V$ . The relationship matrix of APs is replaced by $W=[w_{ij}]$ , $i\in N$ , $j\in N$ , where $w_{ij}$ represents the relationship between AP i and AP j, which can be calculated by

$$\begin{array}{cc}& r_{ij}=\frac{\mathrm{2}{n}_{ij}}{n_i+n_j}.\end{array}$$

(1)

In formula (1), the frequency of AP i and AP j appearing on all users' devices in the same period is counted, denoted as $n_{ij}$ , and the number of times that AP i appears in total is denoted as $n_i$ (the same to $n_j$ ).

Using the greedy algorithm of Kruskal [27], the maximum spanning tree from the graph G is easily got, denoted as T. After choosing a weight λ as the location granularity, the edge in T whose weight is less than λ will be cut down, and leave the tree into some separated connected components. One connected component is regarded as a location. Figure 2 shows the process of constructing the aggregation locations, and a construction with granularity 0.6 is represented in Figure 2(c).

Figure 2

Process of location construction.

In most WLAN datasets, connection is recorded by the format (node, contact time, APs, and signal strength), and one or more APs which a user connects to may appear in one item at the same time, which may cause users' location confusion. Therefore, after getting the set of locations in the mobility scenario, estimating which location the user belongs to in the same period is also needed. The signal strength between a user's mobile device and a WIFI AP in the WLAN dataset can help to solve this problem. A weight between the user and location can be calculated by

$$\begin{array}{cc}& {\mathrm{w}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}}_i=\frac{{\sum }_n^{j=\mathrm{1}}{\mathrm{s}\mathrm{t}\mathrm{r}\mathrm{e}\mathrm{n}\mathrm{g}\mathrm{t}\mathrm{h}}_j}{n}.\end{array}$$

(2)

In formula (2), n represents the number of aps in location i, and strength j represents the signal strength between the user A and AP j ( ${\mathrm{A}\mathrm{P}}_j\in {\mathrm{l}\mathrm{o}\mathrm{c}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}}_i$ ). The user A is considered to be at location i in the time period, if i meets the condition denoted in

$$\begin{array}{cc}& i=\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}\left\{{\mathrm{w}\mathrm{e}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}}_i\right\}.\end{array}$$

(3)

3. Algorithm Design

This paper proposes a simple method for predicting the future locations of mobile nodes, on the basis of their previous ways to other locations. The proposed approach considers different daily time periods, which relates to the fact that users present different behaviors and visit different places during their daily routines. Therefore the hidden Markov model is introduced to capture the dynamism of users' behavior resulting from the daily routines.

What is more, users experience a combination of periodic movement that is geographically limited and seemingly random jumps correlated with their social networks. Social relationships can explain about 10% to 30% of all human movement, while periodic behavior explains 50% to 70% [28]. On the basis of this theory prerequisite, social relationship between nodes is also exploited in this paper for optimization and amendment of location prediction result.

3.1. Hidden Markov Prediction Model

In urban scenario, users adopt different behaviors during different periods of daily time, and the users' daily routines may influence users' trajectories. Thus the different daily time periods (same as daily sample) should be considered in order to guarantee a more realistic representation. With filtering and hidden Markov model, this can be done in a simple way.

Hidden Markov model (HMM) is a well-known approach for the analysis of sequential data, in which the sequences are assumed to be generated by a Markov process with hidden states.

Figure 3 shows the general architecture of an instantiated HMM. Each shape in the diagram represents a random variable that can adopt any number of values. The random variable $x(t)$ is the location state at time t. The random variable $e(t)$ is the daily sample state (in this paper, the observed state is called evidence) at time t. The arrows in the diagram denote conditional dependencies. From the diagram, it is clear that the conditional probability distribution of the location variable $x(t)$ at time t, given by the values of the location variable x at all times, depends only on the value of the location variable $x(t-\mathrm{1})$ , and thus the value at time $t-2$ and the values before it have no influence. This is called the Markov property. Similarly, the value of the evidence   $e(t)$ only depends on the value of the location variable $x(t)$ , at time t.

Figure 3

Example of hidden Markov model.

Given the result of filtering up to time t, one can easily compute the result for $t+1$ from the new evidence $e_{t+1}$ . The calculation can be viewed as actually being composed of two parts: first, the current state distribution is projected forward from t to $t+1$ . Second, it is updated using the new evidence $e_{t+1}$ . This two-part process emerges using

$$\begin{array}{l}P\left(X_{t+\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{e}_{\mathrm{1}:t+\mathrm{1}}\right)\\ \hspace{1em}=\alpha P\left(e_{t+\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{X}_{t+\mathrm{1}}\right){\displaystyle \sum }_{X_t}P\left(X_{t+\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{X}_t\right)P\left(X_t\hspace{0.17em}|\hspace{0.17em}{e}_{\mathrm{1}:t}\right),\end{array}$$

(4)

where α is a normalizing constant used to make probabilities sum up to 1. Within the summation, $P(X_{t+\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{X}_t)$ is the common transition model and $P(X_t\hspace{0.17em}|\hspace{0.17em}{e}_{\mathrm{1}:t})$ is the current state distribution. $P(e_{t+\mathrm{1}}\hspace{0.17em}|\hspace{0.17em}{X}_{t+\mathrm{1}})$ is used to update the transition model and it is obtainable directly from the statistical data.

In participatory sensing system, for each application scenario, the hidden Markov model can be used to predict the future location state of each mobile node. Prediction process includes the following steps.

3.1.1. Preparatory Stage

At the beginning, the system needs to collect enough information of user movement trajectories to construct the Markov chain, and therefore a “warm-up” stage is assumed in the prediction system. During preparatory stage, the system only collects historical data and it cannot provide any predicted information. The warm-up stage can last for one day or one week depending on the amount of information collected.

3.1.2. Determination of State Set

The location elements in the collecting data are extracted and they are denoted as set L. As set L contains a number of location elements, the location of higher visiting frequency is chosen as state set of the system, denoted as set E. If there are m locations in the current scene, the state space can be denoted as $E=\{X_{\mathrm{1}},X_{\mathrm{2}},\dots ,X_m\}$ , and the location i is the ith status $X_i$ of Markov process.

3.1.3. Discretization of Data Set

Statistical data of all users related to state set E is made. Then the data set of each user is processed to be discrete set of the fixed time period, so the set after discretization is denoted as follows:

$$\begin{array}{cc}& \left\{\left(t_k,X_i\right)\right\},\hspace{1em}k=\mathrm{1,2},\mathrm{3}\dots ,\hspace{0.17em}\hspace{0.17em}i\in \left\{\mathrm{1,2},\mathrm{3},\dots ,m\right\}.\end{array}$$

(5)

3.1.4. Calculation of 1-Order Transition Probability Matrix

$n_{ij}$ is the frequency that node A departs from location i for location j, then the probability of node A departing from location i for location j is denoted as

$$\begin{array}{cc}& p_{ij}=\frac{n_{ij}}{n},\end{array}$$

(6)

where n is the total number of time node A departed location i to visit other locations in data set.

Therefore, suppose that there are m locations in the set, an $m\times m$ transition probability matrix is generated as

$$\begin{array}{cc}& P=\left[\begin{array}{cccc}{p}_{\mathrm{11}}& p_{\mathrm{12}}& \cdots & p_{\mathrm{1}m}\\ p_{\mathrm{21}}& p_{\mathrm{22}}& \cdots & p_{\mathrm{2}m}\\ ⋮& ⋮& \ddots & ⋮\\ p_{m\mathrm{1}}& p_{m\mathrm{2}}& \cdots & p_{mm}\end{array}\right].\end{array}$$

(7)

Given $p_j^{(l)}$ as the probability of node on state $X_j$ at initial moment l and computing the probability of each state, the initial distribution of Markov chain can be obtained as

$$\begin{array}{cc}& P\left(l\right)=\left(p_{\mathrm{1}}^{\left(l\right)},p_{\mathrm{2}}^{\left(l\right)},\dots ,p_m^{\left(l\right)}\right).\end{array}$$

(8)

For example, assume that the initial state is $X_2$ , the initial distribution is as $P(l)=\left(\mathrm{0,1},\mathrm{0},\dots ,\mathrm{0}\right)$ , and the absolute distribution at time $l+1$ is as

$$\begin{array}{cc}& P\left(l+\mathrm{1}\right)=P\left(l\right)P=\left(p_{\mathrm{1}}^{\left(l+\mathrm{1}\right)},p_{\mathrm{2}}^{\left(l+\mathrm{1}\right)},p_{\mathrm{3}}^{\left(l+\mathrm{1}\right)},p_{\mathrm{4}}^{\left(l+\mathrm{1}\right)},p_{\mathrm{5}}^{\left(l+\mathrm{1}\right)}\right).\end{array}$$

(9)

3.1.5. Update the Result from the New Evidence

The different daily time periods (daily sample) is regarded as the evidence variable e, so the set of evidences can be defined as $\mathrm{E}\mathrm{V}=\{e^r\}$ , $r=\mathrm{1,2},\dots ,d$ , where d is the total number of daily time period state. For example, break the day into four daily samples $(d=4)$ , and the $\mathrm{E}\mathrm{V}$ is denoted as

$$\begin{array}{cc}& \mathrm{E}\mathrm{V}=\left\{\begin{array}{cccc}\mathrm{a}.\mathrm{m}.,& \mathrm{n}\mathrm{o}\mathrm{o}\mathrm{n},& \mathrm{p}.\mathrm{m}.,& \mathrm{e}\mathrm{v}\mathrm{e}\mathrm{n}\mathrm{i}\mathrm{n}\mathrm{g}\end{array}\right\}.\end{array}$$

(10)

For each daily sample r, a diagonal matrix $O(e^r)$ is defined as

$$\begin{array}{cc}& O\left(e^r\right)=\left[o_{ij}\right],\hspace{1em}\hspace{1em}{o}_{ij}=\left\{\begin{array}{cc}\mathrm{0},\hfill & \mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{i}\mathrm{f}\mathrm{\hspace{0.17em}\hspace{0.17em}}i\ne j\hfill \\ p\left(e^r\hspace{0.17em}|\hspace{0.17em}X=i\right),\hfill & \mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{i}\mathrm{f}\mathrm{\hspace{0.17em}\hspace{0.17em}}i=j,\hfill \end{array}\right.\end{array}$$

(11)

where $P(e^r\hspace{0.17em}|\hspace{0.17em}X=i)=P(e^r,X=i)/P(X=i)=n_i^r/n_i$ , $n_i^r$ represents the frequency of node arriving at location i in the daily sample r, and $n_i$ represents the number of times that node arrives at location i.

Based on all of the above, calculate the probability of node arriving on location i at next time slot $l+1$ using

$$\begin{array}{cc}& P{\left(l+\mathrm{1}\right)}^{\prime }=\alpha O\left(e_{l+\mathrm{1}}^r\right)P\left(l+\mathrm{1}\right)=\alpha O\left(e_{l+\mathrm{1}}^r\right)P\left(l\right)P.\end{array}$$

(12)

It can be considered that the state $X_j$ obtained by the system at time $l+1$ is $X_j=\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}\{p_j^{\left(l+\mathrm{1}\right)}\}$ .

The formula above incorporates a one-step prediction, and it is easy to derive the following recursive computation for prediction of the state at $t+k+1$ from a prediction for $t+k$ ; therefore the state $X_{t+k+1}$ can be obtained by

$$\begin{array}{cc}& X_{t+k+\mathrm{1}}=\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{m}\mathrm{a}\mathrm{x}\left\{P\left(X_{t+k+\mathrm{1}}\right)\right\}.\end{array}$$

(13)

3.2. Social-Aware Prediction Optimization

In participatory sensing system, a mobile node can be the social node carrying data acquisition equipment. Thus, the social relationship is used to estimate the future locations of mobile nodes and optimize the prediction result of hidden Markov model.

In this paper, capturing the evolution of social interactions in the different periods of time (daily sample) over consecutive days is the aim, by computing social strength based on the average duration of contacts.

Figure 4 shows how social interaction (from the point of view of user A) varies during a day. For instance, it indicates a daily sample (8 a.m.–12 p.m.) over which the social strength of user A to users B and C is much stronger (less intermittent line) than the strength to users D, E, and F. Figure 4 aims to show the dynamics of a social network over a one-day period, where different social structures lead to different behavior when a user moves towards the social community that the user is related to.

Figure 4

Contacts a user A has with a set of users in different daily samples $\Delta T_i.$

As illustrated in Figure 4, the total contact time of mobile nodes A and B during a daily sample $\Delta T_i$ in a day k is denoted as

$$\begin{array}{cc}& M_i^k={\displaystyle \sum }_{c=\mathrm{1}}^n\left(t_c^e-t_c^s\right),\hspace{1em}c=\mathrm{1,2},\mathrm{3},\dots ,n,\end{array}$$

(14)

where n is the number of contact times in $\Delta T_i$ , $t_c^s$ indicates the start time of the cth contact of mobile node A and B, and $t_c^e$ indicates the terminate time of the cth contact of mobile node A and B.

Hence the social strength between any pair of nodes A and B in $\Delta T_i$ is denoted as

$$\begin{array}{cc}& W{\left(A,B\right)}_i=\frac{{\sum }_{k=1}^m{M}_i^k}{m\times \Delta T_i},\end{array}$$

(15)

where m is the total number of days in the historical record.

According to formula (15), the social relationship matrix of nodes in $\Delta T_i$ can be obtained. On the basis of relation matrix mobile nodes can be partitioned as communities, which determine the closer relation nodes as a subgroup. Since the users' proximity is only taken into account, partition-based clustering methods, such as k-means and fuzzy c-means, are not applicable. Therefore use a hierarchical clustering method, namely, complete linkage clustering [29], as the community partition algorithm.

Suppose that it used social relationship to calculate the probability of node A arriving at the location i ( $i=\mathrm{1,2},\dots ,m$ ) at next period. Given that node A belongs to community C and the set of other nodes belonging to C on location i at current time slot is denoted as $S=\{S_{\mathrm{1}},\dots ,S_j,\dots ,S_n\}$ , where $S\subseteq C$ , according to conditional probability then the following formula is proposed:

$$\begin{array}{cc}& P_i\left(A\hspace{0.17em}|\hspace{0.17em}{S}_j\right)=\frac{P_i\left(A,S_j\right)}{P_i\left(S_j\right)},\hspace{1em}j=\mathrm{1},\dots ,n,\end{array}$$

(16)

where $P_i(A\hspace{0.17em}|\hspace{0.17em}{S}_j)$ represents the probability of node arriving at location i on the condition that node $S_j$ has already been on the i location; $P_i(S_j)$ represents the probability that node $S_j$ keeps on staying at location, which can be obtained by Markov model calculation; $P_i(A,S_j)$ represents the encounter probability of node A and node $S_j$ on location i and the formula is defined as

$$\begin{array}{cc}& P_i\left(A,S_j\right)=\frac{f_i\left(A,S_j\right)}{{\sum }_{i=1}^m{f}_i\left(A,S_j\right)},\end{array}$$

(17)

where $f_i(A,S_j)$ represents number of encounter times on location i.

Given the relationship weight of node A and node $S_j$ as $W(A,S_j)={\rho }_j$ , the probability of node A arriving on location i at next time slot is

$$\begin{array}{cc}& P_i\left(A\right)={\displaystyle \sum }_{j=\mathrm{1}}^n{\lambda }_j{P}_i\left(A\hspace{0.17em}|\hspace{0.17em}{S}_j\right),\hspace{1em}\hspace{1em}{\lambda }_j=\frac{{\rho }_j}{{\sum }_{j=\mathrm{1}}^n{\rho }_j},\end{array}$$

(18)

where ${\lambda }_j$ is the weight of each conditional probability which is calculated by normalization method, ${\sum }_{j=\mathrm{1}}^n{\lambda }_j=\mathrm{1}$ .

According to the location distribution of all the nodes belonging to C, the probability of node A arriving at different location can be obtained. And combined with the prediction result from hidden Markov model and using weight formula (19) to calculate the probability distribution of node A arriving at all the location in the location set, the location having the maximum of the visiting probabilities is considered as the output of the prediction algorithm:

$$\begin{array}{cc}& P_i={P_i}^{\mathrm{H}\mathrm{M}\mathrm{M}}+d\left(P_i^{\mathrm{s}\mathrm{o}\mathrm{c}\mathrm{i}\mathrm{a}\mathrm{l}}-{P_i}^{\mathrm{H}\mathrm{M}\mathrm{M}}\right),\end{array}$$

(19)

where ${P_i}^{\mathrm{H}\mathrm{M}\mathrm{M}}$ is location prediction probability of state $X_i$ using hidden Markov model, and $P_i^{\mathrm{s}\mathrm{o}\mathrm{c}\mathrm{i}\mathrm{a}\mathrm{l}}$ is the prediction probability of location i based on social relationship, and d is the damping factor which is defined as the probability that the social relation between the nodes helps improve the accuracy of the prediction. This means that the higher the value of d is, the more the algorithm accounts for the social relation between the nodes.

It is beneficial to use social relationship to optimize the prediction result, making the transition probability matrix sparse and improve the accuracy of the prediction model.

4. Experimental Analyses

4.1. Simulation Configuration

In this paper, the experiment data is from the dataset provided by Wireless Topology Discovery (WTD) [30], from which two-month-period data, total 13,215,412 items, is chosen to simulate the prediction algorithm. There are 275 nodes and 524 APs (access points) in the dataset. According to the vicinity of AP positions, the number of locations at which APs are clustered is shown in Figure 5.

Figure 5

Quantity of locations.

Figure 5 shows that when the defined granularity λ becomes bigger, the quantity of the locations in the gained scenario will also become larger. When λ is defined as 1, the quantity of location is equal to the total number of APs. The location granularity λ has been given as 0.5 in following experiment.

4.2. Similar User Clustering

In order to predict the further location of mobile nodes using social relationship, the social network structure in the system should be primarily considered. Based on the quantization formula (15), we calculate the relation strength between any pair of nodes A and B in different daily sample (a.m., noon, p.m., and evening), and the social network structures of the dataset are achieved, illustrated in Figure 6.

Figure 6

Social network structures of the dataset in different daily samples.

A hierarchical clustering method, complete linkage clustering, has been used to cluster mobile users. Figure 6(a) shows the social network clustering result in the a.m. period, and the clustering structures in the period of noon, p.m. and evening are, respectively, illustrated in Figures 6(b), 6(c), and 6(d).

4.3. Prediction Accuracy

In order to evaluate the accuracy of prediction model, the processed node locations can be divided into two parts: using the 50% that has been chosen from the original information to train the Markov model and using the rest as the test case of the prediction model. The prediction precision $P_{\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{u}\mathrm{l}\mathrm{t}}$ is denoted as

$$\begin{array}{cc}& P_{\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{u}\mathrm{l}\mathrm{t}}=\frac{{\sum }_{i=1}^n{\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{y}}_i}{n}.\end{array}$$

(20)

In formula (20), n represents prediction times, and ${\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{y}}_i$ is the prediction result of location i, denoted as

$$\begin{array}{cc}& {\mathrm{a}\mathrm{c}\mathrm{c}\mathrm{u}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{y}}_i=\left\{\begin{array}{cc}\mathrm{1},\hfill & \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{i}\mathrm{s}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{r}\mathrm{i}\mathrm{g}\mathrm{h}\mathrm{t}\hfill \\ \mathrm{0},\hfill & \mathrm{w}\mathrm{h}\mathrm{e}\mathrm{n}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{r}\mathrm{e}\mathrm{s}\mathrm{u}\mathrm{l}\mathrm{t}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{i}\mathrm{s}\mathrm{\hspace{0.17em}\hspace{0.17em}}\mathrm{w}\mathrm{r}\mathrm{o}\mathrm{n}\mathrm{g}.\hfill \end{array}\right.\end{array}$$

(21)

Firstly, the training data set is used to train the prediction model which includes standard Markov model (SMM) and daily-routine-based prediction model (MLPR). Afterward the test cases are used, respectively, to verify the above mentioned two models. The prediction accuracies of the two prediction models are shown in Figure 7, where Figure 7(a) shows the prediction accuracy of nodes from 1 to 92, Figure 7(b) shows the prediction accuracy of nodes from 92 to 184, and Figure 7(c) shows the prediction accuracy of nodes from 185 to 275. From Figure 7, it indicates that the daily-routine-based mobile node location prediction algorithm (MLPR) gains a better performance than standard Markov model. This shows that daily routines can promote the accuracy and improve the algorithm's performance.

Figure 7

Prediction precision of SMM and MLPR.

Then make a comparison among the proposed social-relationship-based mobile node location prediction algorithm using daily routines (SMLPR), O2MM and the ${\mathrm{S}\mathrm{M}\mathrm{L}\mathrm{P}}_N$ . Among these algorithms, second order Markov predictor (O2MM) has the best performance among Markov order-k predictors [15], and social-relationship-based mobile node location prediction algorithm $({\mathrm{S}\mathrm{M}\mathrm{L}\mathrm{P}}_N)$ has the same even better performance than O2MM, which can be obtained from the previous work in the paper [31]. The comparative result is shown in Figure 8, from which it indicates that SMLPR has better prediction effects after combining with daily routines and social relationship and gains a higher accuracy than O2MM and ${\mathrm{S}\mathrm{M}\mathrm{L}\mathrm{P}}_N$ . Figure 9 shows the number of users in different precision range among SMM, O2MM, ${\mathrm{S}\mathrm{M}\mathrm{L}\mathrm{P}}_N$ , and SMLPR, and it illustrates that SMLPR obtained the largest number of node distribution in a higher precision range. For instance, the number of nodes with accuracy greater than 90% in SMLPR is 198 and in O2MM is 114, and SMM only achieves 55 nodes.

Figure 8

Prediction precision of O2MM, ${\mathrm{S}\mathrm{M}\mathrm{L}\mathrm{P}\mathrm{R}}_N$ , and SMLPR.

Figure 9

The number of users in different precision range.

Lastly, the performance of these algorithms is shown as Table 1. The accuracy of SMLPR is 30% higher than the standard Markov model and nearly 10% higher than the second order Markov model. Then a better result could also be obtained in the comparison between SMLPR and ${\mathrm{S}\mathrm{M}\mathrm{L}\mathrm{P}}_N$ .

Table 1

The algorithm performance comparison.

	SMM	O2MM	SMLP ${}_N$	SMLPR
Prediction accuracy	0.6164	0.8275	0.8488	0.9014
Time complexity	$O(N)$	$O(N^2)$	$O(N)$	$O(N)$
Storage space	$O(N^2)$	$O(N^3)$	$O(N^2)$	$O(N^2)$

In the aspects of space cost from Table 1, the complexity of SMLPR is $O(N)$ while O2MM is $O(N^2)$ , and the memory demand of SMLPR is $O(N^2)$ while O2MM is $O(N^3)$ . Thus, it is proved that the SMLPR gets better performance than order-2 Markov predictor at much lower expense, and the SMLPR is more practical than order-2 Markov predictor in the WLAN scenario.

4.4. Impact of Location Granularity

In location-based mobility scenario, location granularity may have a significant influence on the prediction accuracy. In order to evaluate the impact of location granularity, the algorithms' performance is tested by adjusting the granularity value λ, and the result is shown in Figure 10.

Figure 10

The influence of location granularity to prediction accuracy.

As shown in Figure 10, with the increasing of the location granularity λ, due to the number of locations in the scenario, the average accuracies of these four algorithms are relatively decreasing. In these algorithms, SMM and O2MM meet a more significant impact on the factor of location, and the accuracy reduces approximately to 25%. For SMLPR, it shows a relatively moderate downward trend and the location granularity effect to SMLPR is not very obvious.

5. Conclusion

In this paper, the influence of opportunistic characteristic in participatory sensing system is introduced and the problems of sensing nodes such as intermittent connection, limited communication period, and heterogeneous distribution are analyzed. This paper focuses on the mobility model of nodes in participatory sensing systems and proposes the mobile node location prediction algorithm with users' daily routines based on social relationship between mobile nodes. According to the historical information of mobile nodes trajectories, the state transition matrix is constructed by the location as the transition state and hidden Markov model is used to predict the mobile node location with the certain duration. Meanwhile, social relationship between nodes is exploited for optimization and amendment of the prediction model. The prediction model is tested based on the WTD data set and proved to be effective.