# Path Prediction Method for Effective Sensor Filtering in Sensor Registry System

Authors: Sukhoon Lee; Dongwon Jeong; Doo-Kwon Baik; Dae-Kyoo Kim
Journal: International Journal of Distributed Sensor Networks
 (2015)

---

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


---

## Body

## 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. Section2 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, Figure1 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.
(a)
(b)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.Figure2 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.


## 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, Figure1 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.
(a)
(b)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.Figure2 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

Figure3 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.Figure4 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 UPu is the sequential set of locations of u. In Figure 4, the sequence of locations for u is up1→up2→up3→up4→up5 and UPu=up1,up2,up3,up4,up5. 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 cps (e.g., f4=cp1,cp2). 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 cp1 and cp2. The path fragment set (F), which includes a direction for each road, is defined as follows:(1)F=fid∣1≤i≤n,d∈1,-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 directiond of a path fragment f may be either 1 representing forward or -1 representing backward. Therefore, in Figure 4, f4 is expressed as f41=cp1→cp2 and f4-1=cp2→cp1. An undirected path fragment (fi) implies a pair of (fi1,fi-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 (fid).Finally, the set of connected fragments (CFid) defines all the path fragments that are connected to fid. For example, in Figure 4, CF41 represents all the path fragments connected to f41. Because of the direction of f41, CF41 includes all the path fragments starting from cp2 and it is expressed as CF41=f2-1,f51,f71. CFid is defined as follows:(2)CFid=fjd∣fid=cpa⟶cpb,fjd=cpb⟶cpc,fid,fjd⊆F,d∈1,-1.The following list of symbols and their definitions are used in path prediction.Symbols and Definitions for Path Prediction
u: A user
U
s
e
r: A set of users, User=u1,u2,…,un
p: A point, p=latitude,longitude
u
p: A user point, up=latitude,longitude
U
P
u: The set of user points by user
U
P
u: up1,up2,…,upn
c
p: A crossroad point, cp=latitude,longitude
C
P: The set of crossroad points
C
P: cp1,cp2,…,cpn
f
i: The ith path fragment, fi=fi1, fi-1=cpa,cpb
f
i
d: The ith path fragment with direction d
f
i
1: cpa→cpb, fi-1=cpb→cpa
F: The set of all path fragments
F: {f11,f1-1,f21,f2-1,…,fn1,fn-1}
C
F
i
d: The set of path fragment connected with fid.


### 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 locationup 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. Figure5 illustrates a graphical representation of the path fragment identification. To measure the vertical distance between the location up and a path fragment fi, we use an equation that determines the height of a triangle given by three side lengths. f1 is a path fragment between cp1 and cp2 and we calculate a vertical distance (lh1) between up and f1 using three points, up, cp1, and cp2. p1 is the projection of up on f1 and lpr is a length between cp1 and p1. Angles θ1 and θ2 are angles of distance pairs (l1, lf) and (l2, lf), respectively. The vertical distance is measured as follows:(3)distup,f1=lh1=l12-lpr2=l12-l12-l22+lf22lf2,where l12+lf2≥l22 and l22+lf2≥l12.Figure 5
Graphical representation of path fragment identification.u
p is a user point and f1 is a path fragment on which up is projected. Equation (3) has a constraint that both θ1 and θ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., l12+lf2≥l22, l22+lf2≥l12). This enables avoiding infeasible calculations such as the vertical distance between up and f3 which cannot be projected.After calculatinglh1 using (3), we calculate the vertical distance lh2 between up and f2. In comparison, lh1 is shorter than lh2. Thus, f1 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 (idfupd) is defined as follows:(4)idfupd=argminfi∈F⁡distfi,up∩CFprevf,where prevf is the previous path fragment fid before reaching the current path fragment idfupd.


### 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 Section6.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 weightwid of a path fragment fid is defined as follows:(5)wid=the  number  of  moves  alongfid.That is,wid 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 wid 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.Algorithm1 presents a weight-measuring algorithm. Each user (u) has a sequential set of user points (UPu) and acquires the identified path fragment (idfupd) for a user point (up). If idfupd 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 (wid) of idfupd is increased by 1. The algorithm assigns idfupd to prevf.Algorithm 1:Weight-measuring algorithm.
weight_measuring
(1)User  []←get_all_users ( )
(2)for  each  User: u  do
(3)UP  []←get_user_points (u)
(4)prevf← null
(5)for  each  UP: up do
(6)  idf← get_identified_path_fragment (up)
(7)  if  prevf ≠ idfthen // when user moves another path fragment
(8)  i←get_path_fragment_number (idf)
(9)  d←get_path_fragment_direction (idf)
(10)  w[i][d]←w[i][d]+1
(11)  prevf←idf
(12)  endif
(13)endfor
(14)endfor
(15)returnw[][]


### 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 fragmentpfid is defined as follows:(6)pfid=argmaxfjd∈CFid⁡wjd.p
f
i
d represents the path fragment fjd that has the maximum weight wjd. The path fragment is selected from the set of path fragments connected to fid which may be the identified path fragment for the current user point.Figure6 shows an example applying the CBP-PP algorithm. In the figure, a user u has made a sequential move UPu=up1,up2,up3 and is currently located at up3. From the current location, the user may move to up4, up5, or up6.Figure 6
An example of CBP-PP.At all the points ofup1, up2, and up3, the user identifies f11 as the identified path fragment using idfup1. The next path fragment is selected from CF11=f2-1,f31,f41 which is the set of path fragments connected to f11. The weights of the path fragments in CF11 are 30, 15, and 10 and the fragment f2-1 has the highest weight. Thus, f2-1 is selected as the predicted path fragment (pfid).Algorithm2 presents the CBP-based path prediction algorithm. This algorithm uses the up and wid measured in Algorithm 1 and identifies the path fragment (idfupd) currently located by up. Then, the algorithm determines a set of connected path fragments (CFid) with respect to idfupd and selects the path prediction that has the maximum weight wid in CFid as the predicted path fragment (pfid).Algorithm 2:CBP-based path prediction algorithm.
path_prediction (up, w[][])
(1)idf  ←get_identified_path_fragment (up)
(2)CF[]←get_connected_fragments (idf)
(3)pf←null            // predicted path fragment
(4)maxweight  ← 0
(5)for  each  CF: cf  do
(6)  i←get_path_fragment_number (cf)
(7)  d←get_path_fragment_direction (cf)
(8)  if maxweight  <w[i][d] then   // set pf by maximum weight
(9)  maxweight  ←w[i][d]
(10)  pf←cf
(11)  endif
(12)endfor
(13)return  pfThe 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 Table1. 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, CFid,t, wid,t, and pfid,t in consideration of time: (7)F=fid,t∣1≤i≤n,d∈1,-1,t∈T,CFid,t=fjd,t∣fid=cpa⟶cpb,fjd=cpb⟶cpc,fjd∈F,d∈1,-1,t∈T,wid,t=the  number  of  moves  along  a  path  fragmentfidat  a  timet,pfid,t=argmaxfjd,t∈CFid,t⁡wjd,t.Table 1
Time elements and time duration.
T
Time duration
t
1
06:00~08:59
t
2
09:00~11:59
t
3
12:00~12:59
t
4
13:00~16:59
t
5
17:00~18:59
t
6
19:00~21:59
t
7
22:00~05:59Algorithm3 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 wid,t which further elaborates the prediction.Algorithm 3:Weight-measuring algorithm with time.
weight_measuring_with_time
(1)User  []←get_all_users ( )
(2)for  each  User: u  do
(3)UP  []←get_user_points (u)
(4)prevf  ← null
(5)for  each  UP: up  do
(6) idf  ← get_identified_path_fragment (up)
(7) ifprevf  ≠  idf then   // when user moves another path fragment
(8) i←get_path_fragment_number (idf)
(9) d←get_path_fragment_direction (idf)
(10) t←get_current_time ( )
(11) w[i][d][t]←w[i][d][t]+1
(12) prevf  ←  idf
(13) endif
(14) endfor
(15)endfor
(16)returnw[][][]Algorithm4 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 (wid,t).Algorithm 4:CBP-based path prediction algorithm with time.
path_prediction_with_time (up, w[][][])
(1)t←get_current_time ( )
(2)idf←get_identified_path_fragment (up)
(3)CF[]←get_connected_fragments (idf)
(4)pf←null            // pf is a predicted path fragment
(5)maxweight  ← 0
(6)for  each  CF: cf  do
(7)i←get_path_fragment_number (cf)
(8)d←get_path_fragment_direction (cf)
(9)if  maxweight<w[i][d][t]  then   // set pf by maximum weight
(10) maxweight←w[i][d][t]
(11) pf←cf
(12)endif
(13)endfor
(14)return  pf


## 3.1. Path Prediction Process

Figure3 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.Figure4 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 UPu is the sequential set of locations of u. In Figure 4, the sequence of locations for u is up1→up2→up3→up4→up5 and UPu=up1,up2,up3,up4,up5. 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 cps (e.g., f4=cp1,cp2). 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 cp1 and cp2. The path fragment set (F), which includes a direction for each road, is defined as follows:(1)F=fid∣1≤i≤n,d∈1,-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 directiond of a path fragment f may be either 1 representing forward or -1 representing backward. Therefore, in Figure 4, f4 is expressed as f41=cp1→cp2 and f4-1=cp2→cp1. An undirected path fragment (fi) implies a pair of (fi1,fi-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 (fid).Finally, the set of connected fragments (CFid) defines all the path fragments that are connected to fid. For example, in Figure 4, CF41 represents all the path fragments connected to f41. Because of the direction of f41, CF41 includes all the path fragments starting from cp2 and it is expressed as CF41=f2-1,f51,f71. CFid is defined as follows:(2)CFid=fjd∣fid=cpa⟶cpb,fjd=cpb⟶cpc,fid,fjd⊆F,d∈1,-1.The following list of symbols and their definitions are used in path prediction.Symbols and Definitions for Path Prediction
u: A user
U
s
e
r: A set of users, User=u1,u2,…,un
p: A point, p=latitude,longitude
u
p: A user point, up=latitude,longitude
U
P
u: The set of user points by user
U
P
u: up1,up2,…,upn
c
p: A crossroad point, cp=latitude,longitude
C
P: The set of crossroad points
C
P: cp1,cp2,…,cpn
f
i: The ith path fragment, fi=fi1, fi-1=cpa,cpb
f
i
d: The ith path fragment with direction d
f
i
1: cpa→cpb, fi-1=cpb→cpa
F: The set of all path fragments
F: {f11,f1-1,f21,f2-1,…,fn1,fn-1}
C
F
i
d: The set of path fragment connected with fid.


## 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 locationup 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. Figure5 illustrates a graphical representation of the path fragment identification. To measure the vertical distance between the location up and a path fragment fi, we use an equation that determines the height of a triangle given by three side lengths. f1 is a path fragment between cp1 and cp2 and we calculate a vertical distance (lh1) between up and f1 using three points, up, cp1, and cp2. p1 is the projection of up on f1 and lpr is a length between cp1 and p1. Angles θ1 and θ2 are angles of distance pairs (l1, lf) and (l2, lf), respectively. The vertical distance is measured as follows:(3)distup,f1=lh1=l12-lpr2=l12-l12-l22+lf22lf2,where l12+lf2≥l22 and l22+lf2≥l12.Figure 5
Graphical representation of path fragment identification.u
p is a user point and f1 is a path fragment on which up is projected. Equation (3) has a constraint that both θ1 and θ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., l12+lf2≥l22, l22+lf2≥l12). This enables avoiding infeasible calculations such as the vertical distance between up and f3 which cannot be projected.After calculatinglh1 using (3), we calculate the vertical distance lh2 between up and f2. In comparison, lh1 is shorter than lh2. Thus, f1 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 (idfupd) is defined as follows:(4)idfupd=argminfi∈F⁡distfi,up∩CFprevf,where prevf is the previous path fragment fid before reaching the current path fragment idfupd.


## 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 Section6.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 weightwid of a path fragment fid is defined as follows:(5)wid=the  number  of  moves  alongfid.That is,wid 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 wid 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.Algorithm1 presents a weight-measuring algorithm. Each user (u) has a sequential set of user points (UPu) and acquires the identified path fragment (idfupd) for a user point (up). If idfupd 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 (wid) of idfupd is increased by 1. The algorithm assigns idfupd to prevf.Algorithm 1:Weight-measuring algorithm.
weight_measuring
(1)User  []←get_all_users ( )
(2)for  each  User: u  do
(3)UP  []←get_user_points (u)
(4)prevf← null
(5)for  each  UP: up do
(6)  idf← get_identified_path_fragment (up)
(7)  if  prevf ≠ idfthen // when user moves another path fragment
(8)  i←get_path_fragment_number (idf)
(9)  d←get_path_fragment_direction (idf)
(10)  w[i][d]←w[i][d]+1
(11)  prevf←idf
(12)  endif
(13)endfor
(14)endfor
(15)returnw[][]


## 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 fragmentpfid is defined as follows:(6)pfid=argmaxfjd∈CFid⁡wjd.p
f
i
d represents the path fragment fjd that has the maximum weight wjd. The path fragment is selected from the set of path fragments connected to fid which may be the identified path fragment for the current user point.Figure6 shows an example applying the CBP-PP algorithm. In the figure, a user u has made a sequential move UPu=up1,up2,up3 and is currently located at up3. From the current location, the user may move to up4, up5, or up6.Figure 6
An example of CBP-PP.At all the points ofup1, up2, and up3, the user identifies f11 as the identified path fragment using idfup1. The next path fragment is selected from CF11=f2-1,f31,f41 which is the set of path fragments connected to f11. The weights of the path fragments in CF11 are 30, 15, and 10 and the fragment f2-1 has the highest weight. Thus, f2-1 is selected as the predicted path fragment (pfid).Algorithm2 presents the CBP-based path prediction algorithm. This algorithm uses the up and wid measured in Algorithm 1 and identifies the path fragment (idfupd) currently located by up. Then, the algorithm determines a set of connected path fragments (CFid) with respect to idfupd and selects the path prediction that has the maximum weight wid in CFid as the predicted path fragment (pfid).Algorithm 2:CBP-based path prediction algorithm.
path_prediction (up, w[][])
(1)idf  ←get_identified_path_fragment (up)
(2)CF[]←get_connected_fragments (idf)
(3)pf←null            // predicted path fragment
(4)maxweight  ← 0
(5)for  each  CF: cf  do
(6)  i←get_path_fragment_number (cf)
(7)  d←get_path_fragment_direction (cf)
(8)  if maxweight  <w[i][d] then   // set pf by maximum weight
(9)  maxweight  ←w[i][d]
(10)  pf←cf
(11)  endif
(12)endfor
(13)return  pfThe 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 Table1. 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, CFid,t, wid,t, and pfid,t in consideration of time: (7)F=fid,t∣1≤i≤n,d∈1,-1,t∈T,CFid,t=fjd,t∣fid=cpa⟶cpb,fjd=cpb⟶cpc,fjd∈F,d∈1,-1,t∈T,wid,t=the  number  of  moves  along  a  path  fragmentfidat  a  timet,pfid,t=argmaxfjd,t∈CFid,t⁡wjd,t.Table 1
Time elements and time duration.
T
Time duration
t
1
06:00~08:59
t
2
09:00~11:59
t
3
12:00~12:59
t
4
13:00~16:59
t
5
17:00~18:59
t
6
19:00~21:59
t
7
22:00~05:59Algorithm3 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 wid,t which further elaborates the prediction.Algorithm 3:Weight-measuring algorithm with time.
weight_measuring_with_time
(1)User  []←get_all_users ( )
(2)for  each  User: u  do
(3)UP  []←get_user_points (u)
(4)prevf  ← null
(5)for  each  UP: up  do
(6) idf  ← get_identified_path_fragment (up)
(7) ifprevf  ≠  idf then   // when user moves another path fragment
(8) i←get_path_fragment_number (idf)
(9) d←get_path_fragment_direction (idf)
(10) t←get_current_time ( )
(11) w[i][d][t]←w[i][d][t]+1
(12) prevf  ←  idf
(13) endif
(14) endfor
(15)endfor
(16)returnw[][][]Algorithm4 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 (wid,t).Algorithm 4:CBP-based path prediction algorithm with time.
path_prediction_with_time (up, w[][][])
(1)t←get_current_time ( )
(2)idf←get_identified_path_fragment (up)
(3)CF[]←get_connected_fragments (idf)
(4)pf←null            // pf is a predicted path fragment
(5)maxweight  ← 0
(6)for  each  CF: cf  do
(7)i←get_path_fragment_number (cf)
(8)d←get_path_fragment_direction (cf)
(9)if  maxweight<w[i][d][t]  then   // set pf by maximum weight
(10) maxweight←w[i][d][t]
(11) pf←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. Table2 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.5Figure7 shows the data model for implementing the path prediction algorithm. The tableUser is created to identify users and the tableUserPoint is created to store and track user locations and times. To represent roads, crossroad points and path fragments are created in the tableCrossroadPoint andPathFragment, respectively. The tablePathFragmentWeight stores weights for path fragments with a direction and time.Figure 7
Data model for path prediction.Figure8 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.
(a)
(b)
(c)Figure9 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.
(a)
(b)


### 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.Figure10 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.
(a)
(b)


## 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. Table2 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.5Figure7 shows the data model for implementing the path prediction algorithm. The tableUser is created to identify users and the tableUserPoint is created to store and track user locations and times. To represent roads, crossroad points and path fragments are created in the tableCrossroadPoint andPathFragment, respectively. The tablePathFragmentWeight stores weights for path fragments with a direction and time.Figure 7
Data model for path prediction.Figure8 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.
(a)
(b)
(c)Figure9 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.
(a)
(b)


## 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.Figure10 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.
(a)
(b)


## 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 intocoverage,bad coverage, andabsence 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 intonormal calls release representing successful connection andabandoned 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 intopoor,fair, andgood.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. Table3 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 (RAF) 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
PoorService reliability rate (RSR) is the probability of successfully providing services to a mobile device when they are requested. To measure RSR, 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 RAF and provide the requested service to the user. In PP-SRS, the mobile device is also able to receive necessary sensor information according to RAF. 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 (RPA). Therefore, RSR is measured as follows:(8)RSR=the  number  of  Service  Successesthe  number  of  Service  Requests=1-RAF+RAF×RPA,where RAF is the access failure rate and RPA is the path prediction accuracy. Since PP-SRS only uses a path prediction method, RPA is set to zero in SRS evaluation.R
S
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 measuringRSR and counting provided services for a mobile device when services are requested. 106 service requests were used and the simulator stochastically decides by (8) the success or failure of the services.Figure11 shows RSR for SRS and PP-SRS when RAF is 10%, 30%, and 60%. We compare SRS with three cases of PP-SRS with different RPA of 50%, 70%, and 90% for each case. As a result, each system has the highest RSR at RAF 10% and all the three cases of the PP-SRS have a higher RSR than SRS. The higher the RPA of the PP-SRS is, the higher the RSR 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. Figure12 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.
(a)
(b)Figure12(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


## 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 intocoverage,bad coverage, andabsence 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 intonormal calls release representing successful connection andabandoned 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 intopoor,fair, andgood.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. Table3 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 (RAF) 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
PoorService reliability rate (RSR) is the probability of successfully providing services to a mobile device when they are requested. To measure RSR, 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 RAF and provide the requested service to the user. In PP-SRS, the mobile device is also able to receive necessary sensor information according to RAF. 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 (RPA). Therefore, RSR is measured as follows:(8)RSR=the  number  of  Service  Successesthe  number  of  Service  Requests=1-RAF+RAF×RPA,where RAF is the access failure rate and RPA is the path prediction accuracy. Since PP-SRS only uses a path prediction method, RPA is set to zero in SRS evaluation.R
S
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 measuringRSR and counting provided services for a mobile device when services are requested. 106 service requests were used and the simulator stochastically decides by (8) the success or failure of the services.Figure11 shows RSR for SRS and PP-SRS when RAF is 10%, 30%, and 60%. We compare SRS with three cases of PP-SRS with different RPA of 50%, 70%, and 90% for each case. As a result, each system has the highest RSR at RAF 10% and all the three cases of the PP-SRS have a higher RSR than SRS. The higher the RPA of the PP-SRS is, the higher the RSR 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. Figure12 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.
(a)
(b)Figure12(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.


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



---

*Source: 613473-2015-07-16.xml*