WiFi Fingerprint Clustering for Urban Mobility Analysis

The surrounding WiFi AP information, namely MAC address and corresponding received signal strength (RSS) are scanned by the smartphone application, which acquires data at a sampling rate of $5$ minutes to conserve the power, since excessive scanning of WiFi and GPS heavily impacts on mobile phone battery consumption, according to the Android API [26].

The received data in back-end, are processed to understand the indoor POI, neighborhood activity, and micro mobility patterns of the users.

We obtain the GPS based stay points of users, using the data processing pipeline as shown in Figure 2’s GPS stay points extraction module. First, we conduct the data processing of the raw GPS data, which includes components such as removing abnormal, zero distance sequence, and low accuracy GPS location [25]. The abnormal data here includes GPS data with sudden location shift within a short period of time, which can distort the actual path traveled by the users. Zero distance often occurs when the GPS does not receive any signal from the satellite, which causes exact same location for subsequent data. This does not provide any meaningful data for us, and hence we filter it out. The next technique is accuracy filtering, where low accuracy GPS data are removed, that causes high uncertainty in determining the actual location of users. Next, we perform GPS stay point extraction [27, 28] to obtain the list of POIs from a particular user with the timestamp for each visit. Afterwards, we cluster POIs based on their geographical location using DBSCAN to group POI for similar places. This briefly explains the GPS stay points extraction method. After obtaining the raw GPS stay points, we use the duration of the GPS stay points to further detect indoor POI for the users.

Research done in [12] has experimentally evaluated different clustering algorithms, and has chosen DBSCAN [29] as the most suitable method because of its ability to form arbitrary shaped clusters. For indoor POI extraction in this paper, we introduce a modified DBSCAN algorithm to cluster the WiFi RSS measurements (i.e. clustered first using GPS data, as mentioned in Section 2.2). We employ cosine similarity score between two RSS values as the distance metric of the modified DBSCAN algorithm. A cluster (POI) is formed when a user stays for at least $20$ minutes in the same place. Therefore, we choose DBSCAN parameters namely, minimum required points to form a cluster ($minPts$) as $4$ (based on $5$ minute WiFi scan interval), and the cosine similarity threshold ($\epsilon$) to be adaptive, based on the Algorithm 3 (parameter selection is done by experimental evaluation as presented in Table IV). Algorithm 1 explains the procedure of clustering for a given set of WiFi data ($S$), the similarity threshold $\epsilon$, and the minimum points to form a cluster $minPts$. $P$ is the list of output cluster points.

The process of obtaining the neighbour points is shown in Algorithm 2, where inputs are $\alpha$ and $S$, and the output is $N$, which are mentioned in Algorithm 1. The details of the similarity metric is explained in Section 3.1.1. The computation is done separately for each user. The worst case run time complexity for DBSCAN algorithm is $O(n^{2})$, where $n$ is the number of WiFi scan results $(S)$ for a given user.

After getting the final list of clusters, a fingerprint for each cluster (indoor POI) is generated with a unique POI ID (i.e. indoor POI ID is unique to a given GPS stay point). The POI fingerprint ($F$) is denoted as shown in the Equation 3, where $M$ is the MAC address, $R$ is the corresponding average RSS in $dBm$, and $p$ is the number of distinct MAC addresses scanned at that POI.

We collected WiFi and GPS data from a set of users (who use different smartphone models) together with the ground truth labels of the POI they visited. The experimental results for single user and multi user indoor POI extraction are presented in the following subsections.

In order to extract the neighborhood activity from the trajectory, we leverage the concept of sensor fusion to combine GPS and WiFi information sources. The overall process of the neighborhood activity extraction is illustrated in Figure 4.

There are two main data sources used in the processing stage, which are WiFi and GPS stay points. First, we identify the GPS stay points and label them accordingly to understand the characteristics of each GPS POI. Subsequently, we filter it by time to study particular point of interest. Note that while we use a user’s house as point of interest, it could also be an office or any other GPS POI. The filtered GPS stay points will be fused with WiFi stay points to generate GPS+WiFi stay points (WiFi stay points are generated according to Algorithm 1). Among all the GPS and WiFi stay points identified based on the duration of stay, one can easily deduce home or office heuristically, which both are stay points with the longest stay durations. The rest of the GPS and WiFI stay points will be the neighborhood POI. The remaining raw GPS points (moving points) that occurred between neighborhood POI and a specific POI can be further converted into heat maps to capture potential neighborhood activity that does not form a stay point.

As a proof of concept, we perform a simple case study for an user H using WiFi and GPS data for $6$ hours period of the day of 18 September 2019. We compared the methods between different GPS and GPS+WiFi stay points as illustrated in Figure 5(a). We observe that GPS+WiFi stay points data fusion method is able to detect the neighborhood activity, where the GPS stay points method is not capable. Subsequently, visualization of the stay points are shown in Figure 5(b), where gray icons represents traveling GPS data, and pink and green icon denotes home and neighborhood POI. The neighborhood area is located not far away from the residential area, which is less than $100m$. Using only GPS stay points, it may appear that neighborhood activity is almost similar location to stay points, and thus clustering as same stay points. Therefore, we are able to detect the neighborhood activity accurately, using GPS+WiFi data sources, compared to using GPS only as data source.

The results of the neighborhood activity study are presented in the following subsections.

To further study the mobility data using both WiFi and GPS data, we propose a data processing pipeline as shown in Figure 8 below.

Using the trajectory data obtained from the GPS stay points, we perform the timeline extraction to obtain the exact moment of WiFi samples needed to further study micro mobility. Neighborhood WiFi trajectory data are clustered together, using DBSCAN for all users who live in the same neighborhood. WiFi based clustering process is shown in Algorithm 4.

Since we want to identify similar trajectory path, our objective in this scenario is different from that of identifying indoor stay points in Section 3. To understand the micro mobility, we need to identify the travel path, not the stay point. In other words, our objective is to clear up a messy interpretation of GPS map (as shown in Figure 10(a)) into a clearer map (as shown in Figure 10(c)) Therefore, DBSCAN parameters are different in this scenario. We set $minPts=1$ as we need to include every WiFi scan result into the clustering process. Since our sampling rate is low ($5$ min), a user can travel a substantial distance during that time period. Therefore, we want to include every scan result to the clustering process, when identifying the mobility pattern. By evaluating the clustering results, we choose threshold level for cluster formation ($\epsilon$) to provide enough number of clusters to represent the user travel path which reducing the average distance error in WiFi based GPS clusters. Moreover, the number of APs we observe in outdoors are below the low AP level ($A_{L}$).

Once the clustering is completed, we obtain nearest GPS point for each cluster point’s timestamp. If there are more than one member in a particular cluster, we obtain the average of the nearest GPS points with high accuracy (i.e. accuracy $\leq a_{L}=25m$) and represent one WiFi based cluster with one GPS point. If all the members in a cluster indicate low GPS accuracy (i.e. accuracy $>a_{L}=25m$), we get the lowest accuracy value GPS point (which means the highest GPS accuracy), and discard the rest of the members in the cluster.

Figure 9 shows the comparison between the number of clusters, average distance error (in meters) of the cluster points, vs. different threshold values for WiFi based clustering.

We can observe from the Figure 9, that when the threshold value increases the number of clusters also increase and the average distance error decreases. Our objective is to reduce the number of clusters (to obtain a clearer mobility path) and to reduce the average distance error. When $\epsilon=0.25$, we get $140$ clusters with $430.1$ meters of distance error. In contrast when $\epsilon=0.3$, we get $321$ clusters with $241.1$ meters of distance error. Therefore, by considering this trade-off we select $\epsilon=0.3$ as the threshold value for WiFi based clustering. It gives enough number of clusters to represent a messy GPS micro mobility path into a clearer path while having a reduced average distance error.

We study the mobility pattern of $3$ users (denoted as A, B, and L in the Table II) from our study, who live in the same neighborhood (i.e. Simei area in Singapore) and work at the same place (i.e. Singapore University of Technology and Design). Most of the times, these $3$ users commute by walking. The results of the WiFi based clustering is shown in Figure 10. The figure 10(a) shows the raw GPS for $3$ different users, which consists of GPS data points within the travel duration from individual home to work. Note that, each color denotes a separate user L-Purple, A-Yellow, and B-Black, and not all the users have same data amount despite the same timeline, which is from 01 December 2019 to 31 December 2019.

Based on the raw data, we perform data processing as shown in the previous subsection, and cluster the locations, based on WiFi similarities to preserve significant GPS points. A total of $8345$ raw GPS points are simplified into $140$ ($\epsilon=0.25$) and $321$ ($\epsilon=0.3$) clusters as shown in Figure 10(c) and Figure 10(e) respectively, based on WiFi fingerprint clustering method. In other words, each point in Figures 10(c) and 10(e) represents one WiFi based cluster, which is mapped into the nearest GPS point by timestamp. By comparing the Figures, we can observe that WiFi based clustering helps to represent the data in a clearer way, instead of the messy data representation obtained by only using GPS data.

Figure 10(b), Figure 10(d), and Figure 10(f) show zoomed in satellite view of raw gps points shown in the red sqaure area in Figure 10(a), Figure 10(c), and 10(e) respectively. The red square area has a sheltered walkway at the side of the road. By comparing the figures 10(b), 10(d), and 10(f), we can see that when $\epsilon=0.3$, the clustered points are aligned through the walkway. Therefore, WiFi based GPS clustering helps to identify micro mobility patterns of users, which is not possible by only visualizing raw GPS data.