Path Prediction Method for Effective Sensor Filtering in Sensor Registry System

Abstract

The Internet of Things (IoT) has emerged and several issues have arisen in the area such as sensor registration and management, semantic interpretation and processing, and sensor searching and filtering in Wireless Sensor Networks (WSNs). Also, as the number of sensors in an IoT environment increases significantly, sensor filtering becomes more important. Many sensor filtering techniques have been researched. However most of them do not consider real-time searching and efficiency of mobile networks. In this paper, we suggest a path prediction approach for effective sensor filtering in Sensor Registry System (SRS). SRS is a sensor platform to register and manage sensor information for sensor filtering. We also propose a method for learning and predicting user paths based on the Collective Behavior Pattern. To improve prediction accuracy, we consider a time feature to measure weights and predict a path. We implement the method and the implementation and its evaluation confirm the improvement of time and accuracy for processing sensor information.

1. Introduction

The Internet of Things (IoT) has emerged with the advance of networks and embedded software technologies. The IoT is a novel paradigm that is rapidly growing and has a significant influence over application domains such as telecommunications, transportation, and healthcare [1, 2]. Environmental monitoring and context-awareness technologies are required for devices to be connected to each other for communication in the IoT. Particularly, abundant IoT services can be provided in the application domains where various sensors are used. In the IoT paradigm, a sensor network plays an important role as a critical and indispensable infrastructure to provide richer services to users.

In the IoT paradigm, several issues are considered in the Wireless Sensor Networks (WSNs) area. The first issue is registering and managing sensors as the number of sensors increases explosively. To address this, the sensor web has been developed, which enables sharing and browsing sensor data through the web [3]. OGC Sensor Web Enablement (SWE) is a representative specification of platforms that provide sensor information and sensor data on the web [4]. SensorMap [5] and Sensorpedia [6] are significant researches based on SWE. Recently, SensorCloud [7] and OpenIoT [8] have been researched to manage sensors and to provide sensor data using a cloud-computing infrastructure. Through the research, users can receive sensor data wherever needed by mobile device.

The second issue is semantic interpretation and processing. Several works present semantics of sensors [9]. Semantic Sensor Web enhances semantics by adding simply structured sensor metadata to the sensor web [10]. Adding semantic information such as time, space, and theme to sensor metadata enables interpretation of sensor semantics and processing various sensor data by inference [11]. In particular, Semantic Sensor Network Ontology (SSNO) developed by W3C can represent sensor information in various perspectives [12].

The third issue is searching and filtering sensors. Sensor filtering is based on searching specific sensors in the aforementioned platforms for registering sensors such as SensorCloud and OpenIoT. Also, sensor ontologies are used to recognize user contexts and provide user-centric services. Searching specific sensors especially in a large number of entities requires effective sensor filtering technologies. Linked Sensor Middleware (LSM) is a web-based sensor management platform connected to the Semantic Web [13]. LSM uses sensor information such as sensor type and location for searching sensors. Mayer et al. proposed a method for searching sensor information by location using web-based structures of a building [14]. Perera et al. proposed a context-awareness sensor searching technique [15]. Using SSNO, they search relevant sensors for the given context by setting weights of five features including accuracy, reliability, energy, availability, and cost.

The existing sensor searching techniques provide context-aware services including tracking user location. However, these techniques do not consider architectural problems caused by real-time searching or efficiency of mobile networks. Considering applications with location-based services such as iBeacon [16], the existing sensor searching techniques are not sufficient for real-time reaction when the mobile device receives information from a sensor close to the user. Because the mobile device needs to receive sensor information whenever it is requested, the mobile network QoS influences services to be provided successfully to the user.

In this paper, we present a path prediction approach for effective sensor filtering. This approach predicts user paths based on the user location and provides sensor information located nearby the predicted paths to a mobile device beforehand. The path prediction approach can handle real-time situation or mobile network status. The presented method identifies the location of a user using predefined road information and predicts user paths using a simple path prediction algorithm. To implement the method, we use Sensor Registry System (SRS) [17] which registers and shares sensors. For effective sensor searching, the system provides sensor information by tracking the user, predicting user paths, and identifying sensors located near the predicted paths. We also analyze user patterns using a time feature to validate prediction accuracy.

The remainder of the paper is organized as follows. Section 2 describes the problem being addressed in this paper and gives an overview of the presented approach for solving the problem. Section 3 describes the path prediction method for SRS. Section 4 presents the implementation and experiment of the method and Section 5 gives an overview of the existing path prediction algorithms. Section 6 evaluates the method in comparison to the existing work. Section 7 concludes the paper.

2. Problem Definition and Solution Approach

This section discusses several problems in sensor filtering. As a solution for the problems, we present a sensor registering and sharing system, Sensor Registry System (SRS), which is able to search and filter sensors. Then, we extend SRS based on path prediction to resolve the problems.

2.1. Problem Definition

The existing sensor filtering techniques are not suitable for real-time synchronization. Sensor platforms such as SensorCloud and OpenIoT have several problems when they have to support real-time sensor search in the mobile computing environment. One problem is that the performance of personalized sensor search is low because of limited mobile resources. This mandates the sensor filtering process to be worked out on the server side instead of the mobile device. The next problem is that a mobile device using the sensor platforms has to allocate a large amount of resources for requesting and receiving sensor information. This problem makes service process slow when the user wants to provide some services. Therefore, the sensor platforms should send sensor information before request and mobile device immediately uses the information needed. Another problem is that mobile devices are sensitively affected by the mobile network QoS. If a user moves into an unstable network connection area, the mobile device of the user cannot access sensor platforms and, thus, is not able to receive the necessary sensor information. Therefore, the sensor filtering process should recognize the user context, predict needed sensors for the user, and receive sensor information in advance.

To detail the last problem, Figure 1 shows an example of an unstable network connection status situation in the UK network coverage map provided by the EE coverage checker [18]. In Figure 1(a), the green area indicates the 4G mobile network coverage, the purple area indicates the 3G mobile network coverage, and the pink area indicates the 2G mobile network coverage. Figure 1(b) illustrates an example of success and failure in obtaining sensor information when a user moves into an unstable network connection area. Suppose that a user is moving and communicating with the sensor platform in real-time using a 4G mobile device (which is not supported in a 3G mobile communication system). When the user moves along the blue arrow in the 4G coverage area in Figure 1(b), the mobile device successfully connects to the sensor platform and obtains the sensor information. However, when the user moves into the 3G coverage area following the red arrow, the mobile device fails to obtain the sensor information around the user.

Figure 1

UK coverage checker and an example of a problem: (a) 2G/3G/4G coverage map; (b) example of an unstable network connection status problem.

This paper proposes a sensor filtering method that can provide necessary sensors when a mobile device requires sensor information to the sensor platform in real-time while predicting the user paths and sending sensor information nearby predicted paths to the mobile device using the sensor platform.

2.2. Path Prediction Approach

This paper aims at improving sensor filtering in Sensor Registry System (SRS) [17], which is a sensor platform for registering and sharing sensors. SRS was proposed for semantic interoperability between sensors and devices in a heterogeneous sensor network environment [19]. Based on ISO/IEC 11179 [20], SRS registers and manages sensor information. SRS also shares and provides metadata and sensor information such as locations, units, types, and other relevant information (e.g., manufacturer information, installation organization information). SRS enables a mobile device to instantly and directly interpret and process sensor data from heterogeneous sensors.

A primary feature of SRS is that it allows a mobile device to access the system through the Internet and obtain directly sensor data from a sensor network. The mobile device changes its location and communicates with different sensors as the user of the device moves to a different sensor network. However, mobile devices can obtain only raw data from sensors. To address this, SRS provides sensor information for mobile devices to process semantics of raw data.

In this work, we transmit sensor information from multiple sensors simultaneously for rapid services specific to mobile devices. Because SRS receives a request to return the sensor information of one sensor, the mobile device preloads the sensor information of near sensors from the sensor information set created by the proposed approach. Thus, the mobile device can immediately use the sensor information when it is required. This approach is enabled by recognition of user patterns and sensor filtering in advance.

The approach collects user locations, learns movement patterns, predicts user paths, and preloads sensor information of the sensors located near the predicted paths. The mobile device synchronizes with SRS and transmits the current location to SRS. Then, SRS predicts a user path based on the current location and transmits the sensor information set of the sensors located near the predicted path to the mobile device. This enables the mobile device to process services using the preloaded sensor information, even if the user moves into an unstable network connection area.

Figure 2 shows SRS architecture extended by the presented approach. It consists of Sensor Filtering Module, Sensor Information Management, Path Predication DB, and Sensor DB. The Sensor Filtering Module involves user location monitoring, path prediction, and path and sensor matching. The mobile device of a user constantly accesses SRS, which allows SRS to monitor the user location. If the user changes his/her location, SRS predicts the moving path and collects the identifiers of the sensors located near the user. The Sensor Filtering Module connects to the Path Prediction DB and exchanges related data during the process. In Sensor Information Management, the collected sensor identifiers are used to search for sensor information. The sensor information acquired from Sensor DB is returned to the user after SRS creates a sensor information set. In this work, we focus on path prediction for effective sensor filtering in SRS. We also define a time feature for accurate prediction results and evaluate the prediction accuracy.

Figure 2

Extended SRS architecture including the proposed approach.

3. Path Predication Method

This section presents the path prediction method for sensor filtering in SRS. The method is composed of a path identification method and a path prediction algorithm. We first define a set of variables used in the method and then discuss time-based predication.

3.1. Path Prediction Process

Figure 3 illustrates an overview of the path prediction process. Predication involves a set of preprocessing steps. In the preprocessing, SRS loads road information and user history. It then measures the weight of each path fragment which is a unit for path prediction. To store path prediction information, SRS creates a database. Upon completion of the preprocessing, SRS waits for a connection request from the mobile device. When a connection is established, SRS collects the geolocation points (e.g., latitude, longitude) of the mobile device for a specific time duration and identifies the path fragment where the user is currently located. Then, SRS predicts a path fragment that the user might move to using weights measured in the preprocessing.

Figure 3

Overview of the path prediction process.

3.2. Road Definition and Path Fragment

This section describes the representation of a path and a user. The path prediction uses predefined road information. The road that a user can move on is represented by a line. The user location is recognized using the GPS of the mobile device such as latitude and longitude.

Figure 4 shows a graphical representation of roads and user locations. A single point represents a location measured by the GPS and is expressed as a pair p of (latitude, longitude). A user point ( $up$ ) is the location of a user (u) and ${UP}_u$ is the sequential set of locations of u. In Figure 4, the sequence of locations for u is ${up}_1\to {up}_2\to {up}_3\to {up}_4\to {up}_5$ and ${UP}_u=\left\{{up}_1,{up}_2,{up}_3,{up}_4,{up}_5\right\}$ . The blue shadow represents roads on which a user can move and the solid lines in the shadow represent roads. A crossroad point ( $cp$ ) indicating a connection between the roads is represented as a point. A path fragment (f) is a unit of paths and it is represented as a line connection between two $cp$ s (e.g., $f_4=\left({cp}_1,{cp}_2\right)$ ). A path fragment has also a direction (d) based on the user movement history and the direction is decided by selecting a start point between ${cp}_{\mathrm{1}}$ and ${cp}_{\mathrm{2}}$ . The path fragment set (F), which includes a direction for each road, is defined as follows:

$$\begin{array}{cc}& F=\left\{f_i^d\hspace{0.17em}|\hspace{0.17em}\mathrm{1}\le i\le n,\hspace{0.17em}\hspace{0.17em}d\in \left\{\mathrm{1},-\mathrm{1}\right\}\right\},\end{array}$$

(1)

where n is the number of path fragments and d is the direction of a path fragment.

Figure 4

Graphical representation of roads and user locations.

The direction d of a path fragment f may be either 1 representing forward or $-1$ representing backward. Therefore, in Figure 4, $f_4$ is expressed as $f_4^1={cp}_1\to {cp}_2$ and $f_4^{-1}={cp}_2\to {cp}_1$ . An undirected path fragment ( $f_i$ ) implies a pair of ( $f_i^1,f_i^{-1}$ ). In this work, we use predefined road information such as the crossroad points and path fragments for learning and predicting user paths. As the results of prediction, the proposed method returns a predicted path fragment ( $f_i^d$ ).

Finally, the set of connected fragments ( ${CF}_i^d$ ) defines all the path fragments that are connected to $f_i^d$ . For example, in Figure 4, ${CF}_4^1$ represents all the path fragments connected to $f_4^1$ . Because of the direction of $f_4^1$ , ${CF}_4^1$ includes all the path fragments starting from ${cp}_2$ and it is expressed as ${CF}_4^1=\left\{f_2^{-1},f_5^1,f_7^1\right\}$ . ${CF}_i^d$ is defined as follows:

$$\begin{array}{l}C{F}_i^d=\{f_j^d|f_i^d=c{p}_a\to c{p}_b,\hspace{0.17em}{f}_j^d=c{p}_b\hfill \\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\to c{p}_c,\hspace{0.17em}\hspace{0.17em}\left\{f_i^d,f_j^d\right\}\subseteq F,\hspace{0.17em}d\in \{1,\hspace{0.17em}-1\}.\hfill \end{array}$$

(2)

The following list of symbols and their definitions are used in path prediction.

Symbols and Definitions for Path Prediction

•  

u: A user

 

$User$ : A set of users, $User=\left\{u_1,u_2,\dots ,u_n\right\}$

 

p: A point, $p=\left(\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{u}\mathrm{d}\mathrm{e},\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}\mathrm{i}\mathrm{t}\mathrm{u}\mathrm{d}\mathrm{e}\right)$

 

$up$ : A user point, $up=\left(\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{u}\mathrm{d}\mathrm{e},\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}\mathrm{i}\mathrm{t}\mathrm{u}\mathrm{d}\mathrm{e}\right)$

 

${UP}_u$ : The set of user points by user

 

${UP}_u$ : $\left\{{up}_1,{up}_2,\dots ,{up}_n\right\}$

 

$cp$ : A crossroad point, $cp=\left(\mathrm{l}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{t}\mathrm{u}\mathrm{d}\mathrm{e},\mathrm{l}\mathrm{o}\mathrm{n}\mathrm{g}\mathrm{i}\mathrm{t}\mathrm{u}\mathrm{d}\mathrm{e}\right)$

 

$CP$ : The set of crossroad points

 

$CP$ : $\left\{{cp}_1,{cp}_2,\dots ,{cp}_n\right\}$

 

$f_i$ : The ith path fragment, $f_i=f_i^1$ , $f_i^{-1}=\left({cp}_a,{cp}_b\right)$

 

$f_i^d$ : The ith path fragment with direction d

 

$f_i^1$ : ${cp}_a\to {cp}_b$ , $f_i^{-1}={cp}_b\to {cp}_a$

 

F: The set of all path fragments

 

F: $\{f_1^1,f_1^{-1},f_2^1,f_2^{-1},\dots ,f_n^1,f_n^{-1}\}$

 

${CF}_i^d$ : The set of path fragment connected with $f_i^d$ .

3.3. Path Fragment Identification

In this section, we present a method for identifying the path fragment of a user using the location of the user. That is, a location $up$ is projected on a path fragment by the path fragment identification. The projection implies that the user exists on the path fragment which is expressed as a road.

The process of path fragment identification measures the vertical distance between the user point and a path fragment and defines the user located path fragment with the lowest vertical distance. Figure 5 illustrates a graphical representation of the path fragment identification. To measure the vertical distance between the location $up$ and a path fragment $f_i$ , we use an equation that determines the height of a triangle given by three side lengths. $f_1$ is a path fragment between ${cp}_{\mathrm{1}}$ and ${cp}_{\mathrm{2}}$ and we calculate a vertical distance $(l_{h1})$ between $up$ and $f_1$ using three points, $up$ , ${cp}_{\mathrm{1}}$ , and ${cp}_{\mathrm{2}}$ . $p_1$ is the projection of $up$ on $f_1$ and $l_{pr}$ is a length between ${cp}_{\mathrm{1}}$ and $p_1$ . Angles ${\theta }_1$ and ${\theta }_2$ are angles of distance pairs ( $l_1$ , $l_f$ ) and ( $l_2$ , $l_f$ ), respectively. The vertical distance is measured as follows:

$$\begin{array}{l}\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}\left(up,f_{\mathrm{1}}\right)=l_{h\mathrm{1}}=\sqrt{{l_{\mathrm{1}}}^{\mathrm{2}}-{l_{pr}}^{\mathrm{2}}}\\ =\sqrt{{l_{\mathrm{1}}}^{\mathrm{2}}-{\left(\frac{{l_{\mathrm{1}}}^{\mathrm{2}}-{l_{\mathrm{2}}}^{\mathrm{2}}+{l_f}^{\mathrm{2}}}{\mathrm{2}{l}_f}\right)}^{\mathrm{2}}},\end{array}$$

(3)

where ${l_{\mathrm{1}}}^{\mathrm{2}}+{l_f}^{\mathrm{2}}\ge {l_{\mathrm{2}}}^{\mathrm{2}}$ and ${l_{\mathrm{2}}}^{\mathrm{2}}+{l_f}^{\mathrm{2}}\ge {l_{\mathrm{1}}}^{\mathrm{2}}$ .

Figure 5

Graphical representation of path fragment identification.

$up$ is a user point and $f_{\mathrm{1}}$ is a path fragment on which $up$ is projected. Equation (3) has a constraint that both ${\theta }_1$ and ${\theta }_2$ are acute angles because the user point has to be projected on the path fragment. The constraint is measured by the Pythagorean theorem (e.g., ${l_1}^2+{l_f}^2\ge {l_2}^2$ , ${l_2}^2+{l_f}^2\ge {l_1}^2$ ). This enables avoiding infeasible calculations such as the vertical distance between $up$ and $f_{\mathrm{3}}$ which cannot be projected.

After calculating $l_{h1}$ using (3), we calculate the vertical distance $l_{h2}$ between $up$ and $f_{\mathrm{2}}$ . In comparison, $l_{h1}$ is shorter than $l_{h2}$ . Thus, $f_{\mathrm{1}}$ is identified as the user location. To predict the subsequent path fragment of $up$ , we identify the direction of the path fragment. Both the result of the $up$ identification and the path fragment history of the user are required for identifying the direction. The previous path fragment ( $prevf$ ) is the path fragment from which the user is coming. When a path fragment is identified using $prevf$ , it is possible to identify not only the path fragment located by the user, but also the direction along which the user has moved. Given that, the identified path fragment ( ${idf}_{up}^d$ ) is defined as follows:

$$\begin{array}{cc}& {idf}_{up}^d=\underset{f_i\in F}{\arg \hspace{0.17em}\min \hspace{0.17em}}\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{t}\left(f_i,up\right)\cap {CF}_{prevf},\end{array}$$

(4)

where $prevf$ is the previous path fragment $\left(f_i^d\right)$ before reaching the current path fragment $\left({idf}_{up}^d\right)$ .

3.4. Collective Behavior Pattern and Weight Measurement

The proposed path prediction method aims at enabling SRS to provide effective and stable sensor information. SRS should have an acceptable performance in a mobile environment where resources are limited. Also, the path prediction algorithm for sensor filtering does not need to predict entire-range user paths because the path prediction is used only in an unstable network connection area where the network connection of a mobile device might be intermittently disconnected. Therefore, the algorithm should be able to predict close-range path prediction with fast performance in a mobile environment.

There exist several personalized path prediction algorithms (see Section 6.1), but they are not suitable for the above requirements. To satisfy the requirements, we propose a path prediction algorithm based on Collective Behavior Pattern (CBP) [21]. CBP is a concept that a collective behavior influences personal behavior (e.g., Point of Interest). The CBP-based path prediction algorithm (CBP-PP) has lower accuracy than the personalized path prediction algorithms. However, CBP-PP is able to measure weights and predict paths on the server side and it has high performance in a mobile environment. CBP-PP also supports the case where the user has no history in a specific path.

To predict paths based on CBP, we need to learn and measure weights for path fragments. In the preprocessing of measuring weight, we allocate a weight to each path fragment. In this paper, we have the frequency of using a path fragment to be the weight. The weight $w_i^d$ of a path fragment $f_i^d$ is defined as follows:

$$\begin{array}{cc}& w_i^d=\text{the\hspace{0.17em}\hspace{0.17em}number\hspace{0.17em}\hspace{0.17em}of\hspace{0.17em}\hspace{0.17em}moves\hspace{0.17em}\hspace{0.17em}along\hspace{0.17em}\hspace{0.17em}}{f}_i^d.\end{array}$$

(5)

That is, $w_i^d$ indicates how frequently a user has passed along the ith path fragment in the direction of d. Since CBP-PP takes into account all the users, measuring weight involves the move history of all users to be used and the same value is used for $w_i^d$ for all the users. If an individual weight is measured for each user, it requires additional costs for storing different weights for all the path fragments for each user. Therefore, one path fragment has the same weight determined by the path fragment history of all the users.

Algorithm 1 presents a weight-measuring algorithm. Each user (u) has a sequential set of user points ( ${UP}_u$ ) and acquires the identified path fragment ( ${idf}_{up}^d$ ) for a user point ( $up$ ). If ${idf}_{up}^d$ is equal to the previous path fragment ( $prevf$ ), it indicates that the user has not moved into the next path fragment and the algorithm returns and processes the next $up$ to be identified. If it is not equal, it indicates that the user has moved into the next path fragment and, thus, the weight ( $w_i^d$ ) of ${idf}_{up}^d$ is increased by 1. The algorithm assigns ${idf}_{up}^d$ to $prevf$ .

Algorithm 1: Weight-measuring algorithm.

weight_measuring

(1) User   $$[]\leftarrow \text{get\_all\_users}$$ ( )

(2) for  each  User: u  do

(3)    $$UP$$    $$[]\leftarrow \text{get\_user\_points}$$ (u)

(4)   prevf← null

(5)   for  each  UP: up do

(6)      idf← get_identified_path_fragment (up)

(7)      if  prevf ≠ idf then  // when user moves another path fragment

(8)        $$i\leftarrow \text{get\_path\_fragment\_number}$$ (idf)

(9)        $$d\leftarrow \text{get\_path\_fragment\_direction}$$ (idf)

(10)        $$w[i][d]\leftarrow w[i][d]+\mathrm{1}$$

(11)       prevf←idf

(12)      endif

(13)   endfor

(14) endfor

(15) return $$w[][]$$

3.5. CBP-Based Path Prediction Algorithm

The presented path prediction method produces the next path fragment to which the user moves after the currently located path fragment is evaluated for prediction. The method is based on a greedy algorithm that determines heuristic solutions using empirical knowledge. The finding mechanism for a local solution in the greedy algorithm is suitable for close-range path prediction. The use of empirical knowledge in the greedy algorithm can satisfy the requirement that path prediction must be based on collective behaviors, not personal behaviors.

The presented path prediction algorithm compares path fragments by weight and selects one that has the maximum weight as the predicted path fragment using the greedy algorithm. The compared path fragments are then connected to the currently located path fragment of the user. The predicted path fragment ${pf}_i^d$ is defined as follows:

$$\begin{array}{cc}& {pf}_i^d=\underset{f_j^d\in {\mathrm{CF}}_i^d}{\arg \hspace{0.17em}\max \hspace{0.17em}}{w}_j^d.\end{array}$$

(6)

${pf}_i^d$ represents the path fragment $f_j^d$ that has the maximum weight $w_j^d$ . The path fragment is selected from the set of path fragments connected to $f_i^d$ which may be the identified path fragment for the current user point.

Figure 6 shows an example applying the CBP-PP algorithm. In the figure, a user u has made a sequential move ${UP}_u=\left\{{up}_1,{up}_2,{up}_3\right\}$ and is currently located at ${up}_3$ . From the current location, the user may move to ${up}_4$ , ${up}_{\mathrm{5}}$ , or ${up}_6$ .

Figure 6

An example of CBP-PP.

At all the points of ${up}_1$ , ${up}_2$ , and ${up}_3$ , the user identifies $f_1^1$ as the identified path fragment using ${idf}_{up}^1$ . The next path fragment is selected from ${CF}_1^1=\left\{f_2^{-1},f_3^1,f_4^1\right\}$ which is the set of path fragments connected to $f_1^1$ . The weights of the path fragments in ${CF}_1^1$ are 30, 15, and 10 and the fragment $f_2^{-1}$ has the highest weight. Thus, $f_2^{-1}$ is selected as the predicted path fragment ( ${pf}_i^d$ ).

Algorithm 2 presents the CBP-based path prediction algorithm. This algorithm uses the $up$ and $w_i^d$ measured in Algorithm 1 and identifies the path fragment ( ${idf}_{up}^d$ ) currently located by $up$ . Then, the algorithm determines a set of connected path fragments ( ${CF}_i^d$ ) with respect to ${idf}_{up}^d$ and selects the path prediction that has the maximum weight $w_i^d$ in ${CF}_i^d$ as the predicted path fragment ( ${pf}_i^d$ ).

Algorithm 2: CBP-based path prediction algorithm.

path_prediction ( $$up$$ , $$w[][]$$ )

(1) idf   $$\leftarrow \text{get\_identified\_path\_fragment}$$ (up)

(2)  $$CF[]\leftarrow \text{get\_connected\_fragments}$$ (idf)

(3)  $$pf\leftarrow \text{null}$$             // predicted path fragment

(4) maxweight  ← 0

(5) for  each  CF: cf  do

(6)     $$i\leftarrow \text{get\_path\_fragment\_number}$$ (cf)

(7)     $$d\leftarrow \text{get\_path\_fragment\_direction}$$ (cf)

(8)    if maxweight   $$<w[i][d]$$  then    // set pf by maximum weight

(9)      maxweight   $$\leftarrow w[i][d]$$

(10)       $$pf\leftarrow cf$$

(11)     endif

(12) endfor

(13) return   $$pf$$

The approach predicts one path fragment at a time. The algorithm takes into account mobile computing power and human walking speed for accurate results. The approach is effective for predicting short paths supported by the fragmentation of paths. In the case that the amount of sensor information provided by SRS is overly large, a dynamic path revision is required for correct prediction.

3.6. CBP-PP with a Time Feature

CBP which is used as the base for the path prediction algorithm has a limitation that its accuracy is lower than personalized path prediction. To improve accuracy, we consider time in the algorithm. The improved algorithm is named CBP-PP/t. A user makes moves to different locations on certain patterns throughout a day. For example, a user goes to work in the morning, moves out for lunch during the lunch hour, and comes back to home after work in the evening. A similar behavior is observed in many people. This is a type of collective behavior patterns by time. We analyze such patterns in terms of relevant time duration to improve the accuracy of prediction.

Suppose the time elements and time durations in Table 1. We appropriately divide 24 hours into 7 elements by behavior patterns of users. For time analysis, the expression of the path fragment set, the connected path fragment set, and the weight defined above are modified to take into account time. The expression of the predicted path fragment is also modified. The following redefine F, ${CF}_i^{d,t}$ , $w_i^{d,t}$ , and ${pf}_i^{d,t}$ in consideration of time:

$$\begin{array}{l}F=\left\{f_i^{d,t}\hspace{0.17em}|\hspace{0.17em}\mathrm{1}\le i\le n,\hspace{0.17em}\hspace{0.17em}d\in \left\{\mathrm{1},-\mathrm{1}\right\},\hspace{0.17em}\hspace{0.17em}t\in T\right\},\\ {CF}_i^{d,t}=\{f_j^{d,t}\hspace{0.17em}|\hspace{0.17em}{f}_i^d={cp}_a⟶{cp}_b,\hspace{0.17em}\hspace{0.17em}{f}_j^d={cp}_b⟶{cp}_c,\hspace{0.17em}\hspace{0.17em}{f}_j^d\\ \in F,\hspace{0.17em}\hspace{0.17em}d\in \left\{1,-1\right\},\hspace{0.17em}\hspace{0.17em}t\in T\},\\ w_i^{d,t}\\ =\text{the\hspace{0.17em}\hspace{0.17em}number\hspace{0.17em}\hspace{0.17em}of\hspace{0.17em}\hspace{0.17em}moves\hspace{0.17em}\hspace{0.17em}along\hspace{0.17em}\hspace{0.17em}a\hspace{0.17em}\hspace{0.17em}path\hspace{0.17em}\hspace{0.17em}fragment\hspace{0.17em}}\left(f_i^d\right)\\ \text{\hspace{0.17em}at\hspace{0.17em}\hspace{0.17em}a\hspace{0.17em}\hspace{0.17em}time\hspace{0.17em}}\left(t\right),\\ {pf}_i^{d,t}=\underset{f_j^{d,t}\in {\mathrm{CF}}_i^{d,t}}{\arg \hspace{0.17em}\max \hspace{0.17em}}{w}_j^{d,t}.\end{array}$$

(7)

Table 1

Time elements and time duration.

T	Time duration
$$t_{\mathrm{1}}$$	06:00~08:59
$$t_{\mathrm{2}}$$	09:00~11:59
$$t_{\mathrm{3}}$$	12:00~12:59
$$t_{\mathrm{4}}$$	13:00~16:59
$$t_{\mathrm{5}}$$	17:00~18:59
$$t_{\mathrm{6}}$$	19:00~21:59
$$t_{\mathit{7}}$$	22:00~05:59

Algorithm 3 presents the weight-measuring algorithm with time. The algorithm is similar to the algorithm in Algorithm 1. However, the addition of time t details the weight $w_i^{d,t}$ which further elaborates the prediction.

Algorithm 3: Weight-measuring algorithm with time.

weight_measuring_with_time

(1) User   $$[]\leftarrow \text{get\_all\_users}$$ ( )

(2) for  each  User: u  do

(3)    $$UP$$    $$[]\leftarrow \text{get\_user\_points}$$ (u)

(4)   prevf  ← null

(5)   for  each  UP: up  do

(6)     idf  ← get_identified_path_fragment (up)

(7)     if prevf  ≠  idf then   // when user moves another path fragment

(8)       $$i\leftarrow \text{get\_path\_fragment\_number}$$ (idf)

(9)       $$d\leftarrow \text{get\_path\_fragment\_direction}$$ (idf)

(10)       $$t\leftarrow \text{get\_current\_time}$$ ( )

(11)       $$w[i][d][t]\leftarrow w[i][d][t]+\mathrm{1}$$

(12)      prevf  ←  idf

(13)     endif

(14)    endfor

(15) endfor

(16) return $$w[][][]$$

Algorithm 4 describes the CBP-based path prediction algorithm with time. The algorithm also is similar to the algorithm in Algorithm 2, but it uses the time-considered weight ( $w_i^{d,t}$ ).

Algorithm 4: CBP-based path prediction algorithm with time.

path_prediction_with_time ( $$up$$ , $$w[][][]$$ )

(1)  $$t\leftarrow \text{get\_current\_time}$$ ( )

(2) idf   $$\leftarrow \text{get\_identified\_path\_fragment}$$ (up)

(3)  $$CF[]\leftarrow \text{get\_connected\_fragments}$$ (idf)

(4)  $$pf\leftarrow \text{null}$$             // pf is a predicted path fragment

(5) maxweight  ← 0

(6) for  each  CF: cf  do

(7)    $$i\leftarrow \text{get\_path\_fragment\_number}$$ ( $$cf$$ )

(8)    $$d\leftarrow \text{get\_path\_fragment\_direction}$$ ( $$cf$$ )

(9)   if  maxweight   $$<w[i][d][t]$$   then   // set pf by maximum weight

(10)     maxweight   $$\leftarrow w[i][d][t]$$

(11)      $$pf\leftarrow cf$$

(12)   endif

(13) endfor

(14) return   $$pf$$

4. Implementation and Experiment

4.1. System Implementation

To implement the proposed path prediction method, we have developed several applications to be run on the server and mobile devices. On the server side, applications are developed for managing path fragments and user locations, predicting path fragments, and returning the prediction results. On the mobile device side, applications are developed for tracking user locations, displaying identified path fragments from user locations, and verifying path prediction. Table 2 specifies the development environment for the implementation.

Table 2

Development environment.

Feature	Details
OS	Windows 7 Professional K (x86)
Processor	Intel(R) Core(TM) i5-2500 3.30 GHz
RAM	4 GB
Development language	Android, JSP
Mobile OS	Android OS
Android emulator version	4.1.2
Web server	Apache Tomcat 8.0.8
Database	MySQL 5.5

Figure 7 shows the data model for implementing the path prediction algorithm. The table User is created to identify users and the table UserPoint is created to store and track user locations and times. To represent roads, crossroad points and path fragments are created in the table CrossroadPoint and PathFragment, respectively. The table PathFragmentWeight stores weights for path fragments with a direction and time.

Figure 7

Data model for path prediction.

Figure 8 presents screenshots of the implementation on a mobile device. Figure 8(a) displays crossroad points for a path prediction and path fragments connected to each crossroad point. Figure 8(b) shows the sequence of actual user points. Figure 8(c) shows the projection results for the user points on path fragments. As shown in Figure 8(c), it can be confirmed that each user point is correctly identified along path fragments.

Figure 8

Screenshots of implementation: (a) crossroad points and path fragments; (b) sequenced user points; and (c) identified path fragments and projection points.

Figure 9 shows the path prediction results. The blue lines in the figure represent the path fragment currently occupied by the user. On the other hand, the black lines represent the actual path fragments taken after the blue line. The red lines represent the predicted path fragment for the current user location. Figure 9(a) shows the path prediction results without considering time and Figure 9(b) shows the results with time considered. In the figure, we can confirm that time consideration obviously influences the prediction results.

Figure 9

Screenshots of implementation: (a) path prediction result without time; (b) path prediction result with time.

4.2. Experiment

For the experiment, we have also developed a mobile application for tracking user locations, collecting actual user GPS points, and predicting user paths. Five users participated in the experiment. They collected user points by moving around a university campus and near areas for ten days. The user points that are outside of the experiment areas are removed from the collection.

Figure 10 presents the screenshots of the user points used in the experiment. We collected 5871 user points and distinguished 117 datasets from the collection as user paths. Figure 10(a) indicates the collected user points within the university area and Figure 10(b) shows user points near to the university area. The collected user points are used for measuring weights and fed into the path fragment prediction algorithm.

Figure 10

Screenshots of experiment result: (a) user point collection in the university area; (b) user point collection near the university area.

5. Evaluation

This section evaluates the effectiveness of the path prediction-based approach by simulation. It also evaluates the implemented system and the proposed algorithm using the experiment results. First, we discuss an advantage of the extended system, Path Prediction-based SRS (PP-SRS) in comparison to the previous version of SRS. Then, we compare the CBP-based path prediction algorithm (CBP-PP) and the CBP-based path prediction algorithm with the time-considered algorithm (CBP-PP/t) in terms of processing time and accuracy.

5.1. Service Reliability Evaluation

This section describes the comparison SRS and PP-SRS for reliability. A mobile device tries to access SRS or PP-SRS and acquires sensor information in real-time. However, if the device fails to access SRS or PP-SRS due to the low quality of the mobile network, it is impossible for the device to interpret the semantics of sensors, which further disables a user to provide services using sensors. In general, the QoS of the mobile network is evaluated in terms of coverage, accessibility, and audio quality [22]. Coverage is the signal strength received by a mobile terminal. It indicates the probability of network connection of the mobile device at the user location. Coverage is divided into coverage, bad coverage, and absence of coverage by signal strength. Accessibility is the capacity to successfully establish communication calls between two terminals. It is the probability of connection failure by an interruption when a mobile device attempts to connect to a server. Accessibility is divided into normal calls release representing successful connection and abandoned calls representing connection failure. Audio quality is the status of conversation perception during a successful call. It is the probability of receiving unclear answers from a server concerning requested information after the mobile device accesses the server. Audio quality is divided into poor, fair, and good.

A mobile device might fail to access SRS when a user is located in an unstable network connection area. In such an area, the QoS of the mobile network is low in terms of coverage, accessibility, and audio quality. Table 3 shows examples of the QoS factors for high and low quality. Low quality QoS causes frequent failures of access to SRS. That is, a mobile device receives incomplete sensor information from SRS or PP-SRS when it requests. An access failure may occur when any of the QoS factors is of low quality. A ratio of access failure ( $R_{\mathrm{A}\mathrm{F}}$ ) is calculated by dividing the number of access failures by the number of access requests.

Table 3

Mobile network QoS factors and statuses.

QoS factor	High quality	Low quality
Coverage	Coverage	Bad coverage, absence of coverage
Accessibility	Normal calls release	Abandoned calls
Audio quality	Good, fair	Poor

Service reliability rate ( $R_{\mathrm{S}\mathrm{R}}$ ) is the probability of successfully providing services to a mobile device when they are requested. To measure $R_{\mathrm{S}\mathrm{R}}$ , we have developed a simulator to generate access failures when services are requested and we count the number of successful services. In the case of SRS, a mobile device is able to receive immediately necessary sensor information according to $R_{\mathrm{A}\mathrm{F}}$ and provide the requested service to the user. In PP-SRS, the mobile device is also able to receive necessary sensor information according to $R_{\mathrm{A}\mathrm{F}}$ . If the mobile device cannot receive sensor information due to the access failures, it can use preloaded sensor information according to a path prediction accuracy ( $R_{\mathrm{P}\mathrm{A}}$ ). Therefore, $R_{\mathrm{S}\mathrm{R}}$ is measured as follows:

$$\begin{array}{l}{R}_{\mathrm{S}\mathrm{R}}=\frac{\text{the\hspace{0.17em}\hspace{0.17em}number\hspace{0.17em}\hspace{0.17em}of\hspace{0.17em}\hspace{0.17em}Service\hspace{0.17em}\hspace{0.17em}Successes}}{\text{the\hspace{0.17em}\hspace{0.17em}number\hspace{0.17em}\hspace{0.17em}of\hspace{0.17em}\hspace{0.17em}Service\hspace{0.17em}\hspace{0.17em}Requests}}\\ =\left(1-R_{\mathrm{A}\mathrm{F}}\right)+\left(R_{\mathrm{A}\mathrm{F}}\times R_{\mathrm{P}\mathrm{A}}\right),\end{array}$$

(8)

where $R_{\mathrm{A}\mathrm{F}}$ is the access failure rate and $R_{\mathrm{P}\mathrm{A}}$ is the path prediction accuracy. Since PP-SRS only uses a path prediction method, $R_{\mathrm{P}\mathrm{A}}$ is set to zero in SRS evaluation.

$R_{\mathrm{S}\mathrm{R}}$ is the ratio of the number of service successes to the number of service requests. It can be also calculated by the equation about the access successes rate and the prediction success rate after the access failure as shown in (8). If a mobile device successfully accesses PP-SRS, the requested services are provided to the user; on the other hand, if it failed, service providing depends on the rate of path prediction accuracy.

For comparison evaluation, we use a simulator for measuring $R_{\mathrm{S}\mathrm{R}}$ and counting provided services for a mobile device when services are requested. 10⁶ service requests were used and the simulator stochastically decides by (8) the success or failure of the services.

Figure 11 shows $R_{\mathrm{S}\mathrm{R}}$ for SRS and PP-SRS when $R_{\mathrm{A}\mathrm{F}}$ is 10%, 30%, and 60%. We compare SRS with three cases of PP-SRS with different $R_{\mathrm{P}\mathrm{A}}$ of 50%, 70%, and 90% for each case. As a result, each system has the highest $R_{\mathrm{S}\mathrm{R}}$ at $R_{\mathrm{A}\mathrm{F}}$ 10% and all the three cases of the PP-SRS have a higher $R_{\mathrm{S}\mathrm{R}}$ than SRS. The higher the $R_{\mathrm{P}\mathrm{A}}$ of the PP-SRS is, the higher the $R_{\mathrm{S}\mathrm{R}}$ is. If an access failure occurs, the service fails in SRS, whereas PP-SRS is able to successfully provide services using preloaded sensor information through the path prediction. The experiment shows that the proposed PP-SRS is more reliable than SRS.

Figure 11

Service reliability rate of SRS and PP-SRS.

5.2. Processing Time Evaluation

We evaluate the processing time of CBP-PP and CBP-PP/t with ten path fragments with a direction selected from the collected path fragments. We also compare the results of identifying paths and prediction time of CBP-PP and CBP-PP/t. This also shows the overheads caused by the time consideration in CBP-PP/t. Table 4 shows the processing time of CBP-PP and CBP-PP/t and the time difference for the ten selected path fragments. The results show that CBP-PP is faster than CBP-PP/t in all path fragments except one “f006.” The average processing time of CBP-PP is measured as 42.32 ms, while that of CBP-PP/t is measured as 44.41 ms, which results in a 2.09 ms difference. The difference reflects the overhead (4.66% decline) caused by time consideration in CBP-PP/t.

Table 4

Processing time evaluation result.

Path fragment	CBP-PP (ms)	CBP-PP/t (ms)	Difference (ms)
f001	41.52	43.03	1.51
f002	42.11	45.40	3.30
f003	44.65	46.58	1.93
f004	45.30	46.72	1.42
f005	48.18	50.05	1.88
f006	41.02	41.01	−0.01
f007	44.20	48.47	4.26
f008	35.93	40.79	4.86
f009	41.02	42.06	1.03
f010	39.28	39.97	0.69
Average	42.32	44.41	2.09

5.3. Accuracy Evaluation

The evaluation of accuracy is concerned with measuring the accuracy of the predicted path fragment using the datasets collected by the five users. Figure 12 presents the accuracy comparison of CBP-PP and CBP-PP/t. The user path for the prediction test is not considered in the evaluation.

Figure 12

Accuracy evaluation result: (a) user paths = 50 datasets; (b) user paths = 116 datasets.

Figure 12(a) shows the accuracy of CBP-PP and CBP-PP/t for 50 datasets. CBP-PP shows 24.8% accuracy on average and CBP-PP/t shows 43% accuracy on average. Figure 12(b) indicates the accuracy for 116 datasets. The average accuracy of CBP-PP is 55.6%, while that of CBP-PP/t is 87.4%. In both cases, CBP-PP/t shows a higher accuracy than CBP-PP, which confirms that time consideration improves the accuracy of path predication. Table 5 shows the accuracy of CBP-PP and CBP-PP/t and the difference rate for 116 datasets. The result confirms that the accuracy of CBP-PP/t is 64.6% on average superior to CBP-PP.

Table 5

Accuracy evaluation result table for 116 datasets.

User	CBP-PP (%)	CBP-PP/t (%)	Difference (pp)
u001	45	89	98
u002	70	90	29
u003	38	75	97
u004	50	83	66
u005	75	100	33
Average	55.6	87.4	64.6

6. Related Work

This section presents related work about path prediction research. We describe personalized pattern-based path prediction research using personal location tracking data and discuss problems of the existing work in applying them to extending SRS. We also discuss the work on Collective Behavior Pattern- (CBP-) based path prediction using location tracking data of groups.

6.1. Personalized Pattern-Based Prediction

Numerous techniques have been studied for predicting locations or paths using user mobility [23–25]. The majority of the existing research uses probabilistic models along with context-awareness and data mining techniques. They also use personalized path prediction using variable user information.

Samaan and Karmouch [23] proposed an architecture for predicting personal mobility using contextual knowledge and a spatial conceptual map. Given a user context and an area of interest defined on a map, the system predicts a user location using the Dempster-Shafer theory. The system returns a predicted path created by searching a path from the current location of the user to the predicted location. The prediction result is only influenced by user profiles and defined rules. So the prediction result cannot be improved by data collection such as the user mobility data and system experiences.

Chen et al. [24] presented a personal route prediction system that stores user location data from GPS and predicts paths by learning the data. It defines Regions of Interest (ROI) as a criterion, which is the staying time of the user. It creates a basic Markov model based on frequency. The Markov model is then used to predict paths from the current location. They divide a map into cells and provide patterns moving towards the ROI of the users. Unlike our work, they do not predict detailed paths.

Kim et al. [25] described a probabilistic graphical model that acquires user location data from GPS. It uses a prediction approach similar to that in the work by Chen et al. The model includes processes for combining several paths that have high similarity in path learning.

The existing research is based on user data for prediction. If a user moves to a new area (e.g., touring), personalized learning is very hard since there exist no training datasets for the user.

6.2. Collective Behavior Pattern-Based Prediction

There are some works (e.g., [21, 26]) based on CBP for addressing the personal pattern problem in Section 6.1. CBP is based on that collective behaviors influence personal behaviors, which enables predicting user locations and moves. A CBP-based method can predict paths using the information of people that have visited an area even if there is no history for a specific user [21].

Xiong et al. [26] proposed a prediction method based on collective behavioral patterns. This method predicts user locations based on the cell tower id of a phone. They use a hybrid method of CBP and personalized patterns. However, the method cannot provide detailed user paths since it can predict only cell towers.

CBP-based methods have two advantages. Firstly, they can predict a user path using group location data without the user location data. Also their prediction is fast at the group level. However, group-level models often cause low accuracy because it does not analyze the personal pattern. This motivated the hybrid method of the CBP-based method and personalized pattern-based model by Xiong et al.

7. Conclusion

The Internet of Things (IoT) has emerged and systems for registering and managing sensor information have advanced. SRS is developed to dynamically support sensor information and accurately process the semantics of heterogeneous sensors. As the number of sensors in the IoT environment increases explosively, so does the importance of sensor filtering in sensor management systems.

There have been several sensor filtering problems arisen in mobile computing environments such as low performance, low resource, and unstable network status. Searching sensors in real-time requires a rapid connection and process and providing services consistently and immediately regardless user mobility. To address this, we have presented a path prediction method for effective sensor filtering. In the method, we use SRS as the sensor platform for providing sensor information. We have described path representation, identification, and prediction algorithms for path prediction. The presented path prediction algorithm is based on CBP and takes into account time. We evaluated the algorithm by implementing it in SRS and PP-SRS and compared the outputs. We also evaluated the processing time and accuracy of prediction between the CBP-PP algorithm and CBP-PP/t algorithm. The evaluation shows that CBP-PP/t takes a longer processing time on average than CBP-PP, which is attributed to the overhead of time consideration. However, the difference is slight. On the other hand, CBP-PP/t demonstrates significantly higher accuracy in prediction over CBP-PP.

In the future, we plan to implement SRS and evaluate the connection performance with SRS. We also plan to develop a hybrid path prediction algorithm including CBP-based and personalized approaches to improve the accuracy of the prediction.