Patent Description:
Wi-Fi, based on the IEEE <NUM> standard, is one of the most pervasive technologies in today's society. There are more than <NUM> billion Wi-Fi devices in the world, and this trend is only increasing. It is therefore very interesting to use WiFi technology for much more than just communicating over the Internet. Indeed, in recent years there has been a great deal of interest in the industry in the possibility of performing analytics such as passive device counting, segmentation according to visiting patterns, location, tracking, density heat maps, etc..

Wi-Fi devices broadcast wireless signals with a certain cadence that can be captured by nearby access points (APs). The access points listen to these signals and report the RSSI (Received Signal Strength Indicator), which indicates the received power. These signals, in the form of management frames called "Probe Request", are used by devices (smartphones, tablets, laptops, etc.) to discover new Wi-Fi networks nearby, as well as to search for those they already know. In these messages, devices announce their capabilities, what they expect to find on nearby networks, the speeds they support, etc. In addition, the probe request frames include an identifier of the sending device, the source MAC address.

Patent document <CIT> discloses a method of identifying a Wi-Fi device using a particular combination of SSIDs sent by the Wi-Fi device as a device signature.

A Wi-Fi analytics system could gather the probe requests using the access point's radios, and then build interesting statistics with this accurate data (e.g. device identification for counting or tracking). Unfortunately, there are several problems that cause conventional WiFi analytics systems to have very low accuracies and significant distortion in the data, rendering the metrics that are built with them useless. The two fundamental problems are:.

It is clear that neither of these two options provides robust and reliable data against the MAC randomization problem. And this behaviour will only increase in the coming years until devices with static (real) MACs disappear. There is a need for a technology capable of building stable and robust identifiers of the devices around it, as MAC addresses are no longer reliable for applications such as counting, location, tracking, segmentation, etc..

Patent document <CIT> tries to solve this problem, by performing a cluster analysis on a time series of the sequence numbers included in the header of the probe request frames. The invention described in this patent document works fine when the sequence numbers of the probe request frames are sequentially used by the Wi-Fi devices (e.g. sequence numbers: <NUM>, <NUM>, <NUM>, etc.). However, many Wi-Fi devices are currently sending random sequence numbers (e.g. sequence numbers: <NUM>, <NUM>, <NUM>, etc.), and for these Wi-Fi devices the cluster analysis of <CIT> document would not properly work.

The present invention solves this problem, by unambiguously identifying Wi-Fi devices that are not connected to a Wi-Fi network and employ MAC address randomization, even when they use random sequence numbers in their probe request frames.

The present invention relates to a method and system for identifying Wi-Fi devices that solves the aforementioned problems.

According to an embodiment, the cluster analysis includes computing the maximum distance in the N-dimensional RSSI space of two points of any cluster to obtain a spread scoring; and if the spread scoring is higher that a clustering threshold, incrementing the number of clusters by one. The clustering threshold is preferably a value trained using training probe requests frames received by the plurality N of access points, wherein the training probe request frames contain real MAC addresses of Wi-Fi devices.

In an embodiment, the cluster analysis is performed on the averaged RSSI measurements received by each access point within a determined time window. The temporal span of the time window is preferably trained using training probe requests frames received by the plurality N of access points, wherein the training probe requests frames contain real MAC addresses of Wi-Fi devices.

The system for identifying Wi-Fi devices is defined in claim <NUM>.

A series of drawings which aid in better understanding the invention and which are expressly related with an embodiment of the said invention, presented as a non-limiting example thereof, are very briefly described below.

The present invention refers to a method and system for identifying Wi-Fi devices. The present invention presents a novel solution to the problem of identifying non-associated WiFi devices that randomise their MAC address.

<FIG> depicts a flow diagram of a method <NUM> of identifying Wi-Fi devices according to an embodiment. The method <NUM> comprises receiving <NUM>, by a plurality N of access points, probe request frames <NUM> sent by Wi-Fi devices. The Wi-Fi devices are not associated with the access points and, therefore, their identity is unknown since the devices normally use random MAC addresses.

For each probe request frame <NUM> received at an access point, the access point generates <NUM> an associated fingerprint <NUM>. The fingerprint generation comprises extracting a set of features from a plurality of fields of each probe request frame <NUM> and assigning a fingerprint <NUM> to each probe request frame <NUM> based on the extracted set of features.

The plurality N of access points then send <NUM> the generated fingerprints <NUM> to a server. For each fingerprint <NUM>, the access points also send a timestamp and an RSSI (Received Signal Strength Indicator) measurement corresponding to the probe request frame <NUM> to which the fingerprint <NUM> is associated.

The server identifies <NUM> bursts <NUM> of probe request frames using their associated timestamps. For each burst of probe request frames, the server determines <NUM> an averaged RSSI measurement <NUM> received by each access point. For each fingerprint, the server performs an N-dimensional cluster analysis <NUM> on the averaged RSSI measurements received by each access point, obtaining at least one cluster <NUM> per fingerprint <NUM>. Finally, the server identifies <NUM> a Wi-Fi device for each different cluster <NUM>, obtaining a list of identified Wi-Fi devices <NUM>.

<FIG> shows a block diagram of a system <NUM> for identifying Wi-Fi devices according to an embodiment. The system <NUM> comprises a plurality N of access points (AP<NUM>, AP<NUM>,. , APN) arranged at an installation <NUM> (e.g. a shopping centre, a school, a beach) and a server <NUM>.

The system can be divided into two fundamental stages:.

With regard to the fingerprint generation, the access points (AP<NUM>, AP<NUM>,. , APN) are configured to receive probe request frames <NUM> sent by Wi-Fi devices <NUM> (also called "stations") and generate a fingerprint <NUM> associated to each probe request frame <NUM>. Each access point locally generates a compact fingerprint from all the possible information present on each received probe request frame <NUM>. It works for non-associated Wi-Fi devices <NUM> (with and without random MAC addresses), but its utility as a unique identifier of the Wi-Fi device <NUM> becomes more important when the MAC address is no longer reliable (i.e. when the MAC address is randomized).

The fingerprint <NUM> is generated by hashing specific information within the probe request frame <NUM>. In an embodiment, a hashing algorithm having a reduced size and high entropy (ability to compress data) is preferably used. The access points gather probe request frames <NUM>, extract their information elements (IEs) and make a footprint of those elements. Different hashing algorithms and methods for generating fingerprints may be used, such as the one disclosed in patent document <CIT>.

From all of the information elements present in a probe request frame <NUM>, not all of them are used, but only those that are invariant for the same device. The information elements that can vary may be used, but only partially: it is only checked if they are present, but not their value. All this information is concatenated and passed through a hashing algorithm that returns the final fingerprint. Fingerprints in the <NUM> band are preferred, because they are richer, but the same process may be done for fingerprints in the <NUM> band (with fewer information elements).

In an embodiment, the information elements used are the following:.

The information elements whose content can vary but can be partially used are:.

As a final information, it is checked whether the OUI (Organizationally Unique Identifier, the first three bytes of a MAC address) of the MAC address is a known fixed random prefix, like Google's da:a1:<NUM>. However, the vast majority of current MAC addresses randomise <NUM> of the <NUM> bits that constitute the MAC address. In an embodiment, the applied hashing algorithm is a <NUM> bit Fowler/Noll/Vo FNV-1a, which provides great balance between simplicity, portability, speed, low collisions and good distribution.

<FIG> depicts, according to an embodiment, the fingerprint generation <NUM> using a hashing algorithm <NUM> on each access point. The input of the hashing algorithm <NUM> is a set of information elements <NUM> of the probe request frames <NUM> received at the access points. The output of the hashing algorithm <NUM> is a fingerprint <NUM> that condense and clean the information gathered on each probe request. As previously explained, other different fingerprint generation methods may be employed.

The next step includes cloud upload and storage <NUM>. This step consists of each access point uploading the fingerprints <NUM> to a cloud database (e.g. memory <NUM> at the server <NUM>). The fingerprint uploading may be carried out in real time, as they are generated. The access points also upload some additional metadata, such as a timestamp or an RSSI (Received Signal Strength Indicator) measurement of the corresponding probe request frame <NUM>. This data is stored in a table as they arrive at the server <NUM>. The rows of the table are sorted according to the timestamp.

The next step, preprocessing, is performed at a processing unit <NUM> of the server <NUM>. The goal of the preprocessing is to have multiple quasi-simultaneous RSSI readings for each received fingerprint, to identify which probe request frames <NUM> have been received by different access points, so that the RSSIs can be grouped and treated in the next stages. To achieve this goal, two main steps are performed: burst identification and burst binding.

A burst is a group of probe request frames <NUM> sent by a Wi-Fi device <NUM> in a very short period (in the order of milliseconds), to achieve redundancy. In this period, the MAC address is consistent. The number of probe request frames sent per burst by a Wi-Fi device <NUM> and the span of time between consecutive bursts depend on each Wi-Fi device <NUM> and its circumstances: battery level, OS version, driver version, etc..

In real scenarios, it is a common event that some frames of the burst are lost while others reach the access point, due to possible interference, multi-pathing, or collisions. This is shown in the scheme depicted in <FIG>: a Wi-Fi device <NUM> sends two probe request frames <NUM> in every channel (i.e. a burst <NUM> of probe request frames), and different possible results might occur. For access point A, one of the probe request frames <NUM> suffer a collision (highlighted with a lightning symbol) and it gets lost, while the other probe request frame <NUM> is received. For access point B, both probe request frames <NUM> are received correctly, but in the case of access point C, both probe request frames <NUM> are lost due to the distance between access point C and the Wi-Fi device <NUM>. Therefore, only access point B has received the first probe request frame. If a one-to-one probe request association was made, the record would imply that the Wi-Fi device <NUM> is far from access point A and access point C, as none of them received the first frame, but this would a wrong assumption. Therefore, a solution is to aggregate the received probe request frames <NUM> for each access point and each burst <NUM>.

This way, the first step in the pre-processing includes identifying the different received bursts <NUM> for each access point. This can be made, for instance, by locating the frames with the same MAC address received by the same access point in the last second (or other configurable span of time), as no Wi-Fi device <NUM> sends multiple bursts in that short interval of time. These probe request frames <NUM> are grouped and their RSSI measurements and timestamps are averaged. This step is called burst identification.

<FIG> depicts an exemplary embodiment of burst identification <NUM>. The processing unit <NUM> of the server <NUM> receives several fingerprints associated to probe request frames in a short time, including an associated timestamp <NUM>, a MAC address <NUM>, an access point identifier <NUM> (i.e. the access point which sent this data to the server <NUM>) and an RSSI measurement <NUM> of the corresponding probe request frame. This data is stored in a table <NUM>, wherein each row corresponds to a different fingerprint (the fingerprint is not shown in the columns). The probe request frames are grouped for each access point, and the RSSI measurements and timestamps are averaged. For instance, for access point <NUM> there are two probe request frames received within <NUM> miliseconds, a time interval shorter than <NUM> second, and the RSSID measurements <NUM> (-<NUM> and -<NUM> dBm) are averaged to -<NUM> dBm (averaged RSSI measurement <NUM>) and the timestamps <NUM> (<NUM>:<NUM>:<NUM> and <NUM>:<NUM>:<NUM>) are averaged as well (<NUM>:<NUM>:<NUM>).

After that, burst binding <NUM> is carried out, where the averaged RSSI measurements <NUM> of the bursts received in different access points are compared, looking for cases where in an interval of few seconds a burst with the same MAC address is received in different access points. As the temporal span is small, it is supposed that it is the same group of probe request frames (i.e. burst <NUM>) received by different access points, and the measurements are grouped in a table for a proper analysis in the next stage. For instance, in <FIG> all the averaged RSSID measurements <NUM> corresponding to a same burst <NUM> are associated and joint together in a single row of a table. In this example, the first (i.e. older) timestamp is used for the burst <NUM> and the RSSI measurement corresponding to access point <NUM> is kept empty, since no measurement was received by this access point.

Finally, an optional step of filtering the grouped bursts can be carried out, dropping every burst whose maximum captured RSSI is below some determined clustering threshold, in the order of -<NUM> dBm. The aim of this cleaning is to ensure that the user identification will be performed in an area close to the access points, within the installation <NUM> where the access points are arranged.

The resulting data structure of the pre-processing step <NUM> is represented in the table <NUM> depicted in <FIG>, wherein each row represents a different identified burst (aggregated burst <NUM>). In the table <NUM>, N represents the number of access points in the group, M is the number of captured bursts <NUM>, K is the number of unique MAC addresses <NUM>, and F is the final number of unique fingerprints <NUM>. The expected relation between these numbers is that M is greater than or equal to K, which in turn is also greater than or equal to F. They will be equal only if each captured burst comes from totally different devices, hence their fingerprint will be different too. In the table <NUM>, xi,j represents the averaged RSSI measurement of the burst i received by the access point APj, but if no probe request frame <NUM> of that burst <NUM> is captured by an access point, then xi,j is fixed to the minimum RSSI acquired in a real scenario, which is usually in the order of -<NUM> dBm.

The purpose of the post-processing step <NUM> performed by the processing unit <NUM> is to identify which of the obtained fingerprints (fp<NUM>, fp<NUM>,. , fpF) is actually masking multiple devices and to separate their probe request frames in order to acquire statistics and analytics for device counting or device tracking. The post-processing is carried out on the aggregated bursts <NUM> in a time window basis.

The temporal span of the time window is a variable design that will depend on the expected number of users. In an embodiment, the default value of the time window is set out to five minutes. The aggregated bursts <NUM> within each time window are split depending on the MAC address, whether it is randomized or it is a real (static) one. If it is a real MAC, the measured RSSI can be directly employed on a location algorithm based on true-range multilateration. Therefore, analytics are trivial in that case.

However, most of modern devices randomize their MAC address so a deeper analysis needs to be implemented. <FIG> shows the scatter plot of aggregated bursts <NUM> received from probe request frames with random MAC address, as viewed by two access points (AP<NUM>, AP<NUM>) in the installation <NUM>. Without the segmentation by fingerprints, it is hard to know how many devices have produced all these aggregated bursts <NUM>.

In a next step, the aggregated bursts <NUM> are grouped by their fingerprints <NUM>. Next, each group is examined and clustered (if needed) following the flowchart depicted in <FIG>. For each fingerprint (fp<NUM>, fp<NUM>,. , fpF), an N-dimensional cluster analysis is performed on the averaged RSSI measurements (xi1, xi2,. , xiN) <NUM> received by each access point (AP<NUM>, AP<NUM>,. , APN), obtaining at least one cluster <NUM> per fingerprint <NUM>.

The output is a list of labels (list of identified Wi-Fi devices <NUM>) identifying which aggregated bursts <NUM> correspond to the same Wi-Fi device <NUM> by studying the cadence, burst pattern, and the RSSI matrix.

<FIG> show an example of input (<FIG>) and output (<FIG>) of the clustering process applied to a fingerprint fpi for an installation <NUM> with two access points AP<NUM> and AP<NUM> (N=<NUM>). On <FIG>, the probe request scatter plot including the aggregated bursts <NUM> is received. At first glance it can be seen that there are two clear clusters of aggregated bursts <NUM>, although in other cases (especially when N><NUM>) it will not be obvious. On <FIG> the result of the unsupervised clustering process is shown, in which two different clusters <NUM> are identified and therefore it is determined that in this time window this same fingerprint fpi is masking two different Wi-Fi devices <NUM>. A system that only counts one Wi-Fi device <NUM> per fingerprint <NUM> would be wrong in this case.

According to the embodiment of <FIG>, the cluster process includes the following steps:.

For the cluster analysis <NUM> many clustering methods can be applied, such as a k-means analysis, which clusters data with the purpose of obtaining K groups of equal variance, minimizing the inertia, which is the sum of the squared distance from each point of a cluster to its centroid. It always converges but in order to achieve the global minimum, and not a local minimum, the initialization is key. Therefore, the computation of the clusters is carried out several times with different initial centroids. As an improvement of this implementation, k-means++ scheme was developed (<NPL>), and it reduced the issues with the initialization process. K-means is a good choice for this application because the variance of the RSSI of the probe request frames is similar for pseudo-static devices in an area. When the devices are moving, the variance will grow, but as the analysis is done in a temporal basis, the time window can be shortened if the devices are supposed to be in motion. In scenarios where devices have disparate behaviour, hence different variances in RSSI of the probe request frames, other clustering methods can be used, such as a hierarchical clustering algorithm.

<FIG> shows an example of scatter plots of aggregated bursts <NUM> as viewed by five different access points (AP<NUM>, AP<NUM>, AP<NUM>, AP<NUM>, AP<NUM>) in the installation <NUM>, grouped in pairs of access points. In this case N=<NUM>, and the cluster analysis <NUM> in 5D is performed directly working in the <NUM>-dimensional space, without the need to do it using the 2D planes shown in the figure. <FIG> shows the resulting planes if the "5D point cloud" is projected on each plane formed by a pair of access points (AP<NUM>-AP<NUM>, AP<NUM>-AP<NUM>, etc), only for illustration.

The clustering is therefore performed directly in a N-dimensional space using the Kmeans++ algorithm with a determined clustering threshold, which is preferably trained from real data. The cluster analysis may include computing the maximum distance, in the N-dimensional RSSI space, of two points of any cluster, obtaining a spread scoring <NUM>. It is then checked <NUM> whether the spread scoring <NUM> is higher that a clustering threshold, and in that case the number of clusters NC is incremented by one.

In an embodiment, the cluster analysis is performed on the averaged RSSI measurements <NUM> received by each access point (AP<NUM>, AP<NUM>,. , APN) within a determined time window.

The clustering threshold and/or the temporal span of the time window may be values trained using training probe requests frames received by the plurality N of access points (AP<NUM>, AP<NUM>,. , APN), wherein the training probe requests frames contain real MAC addresses of Wi-Fi devices <NUM>.

To obtain the best results in the post-processing step <NUM>, it is very important to tune the system parameters to match the characteristics of the scenario (expected number of devices, user patterns, mobility, etc.). It is evident that in a mall the expected number of Wi-Fi devices is higher than in a regular office; besides, the Wi-Fi devices will move more often in the first scenario than in the last one. The parameters that need to be calibrated are the temporal span of the time window and the clustering threshold for the maximum distance within one cluster. This adjustment can be conducted manually. However, the probe request frames from the real MAC Wi-Fi devices could be exploited in a training system that would find the optimal values, with the supposition that these real MAC Wi-Fi devices behave in a way similar to the randomized MAC Wi-Fi devices.

A training process according to an embodiment to obtain a clustering threshold and/or a temporal span of the time window is depicted in <FIG>. According to this figure, the probe request frames <NUM> received with real MAC addresses and random MAC addresses follow different paths. The upper branch <NUM> corresponds to the process already described in <FIG> for random MAC addresses (fingerprint generation <NUM>, cloud upload and storage <NUM>, pre-processing <NUM> and post-processing <NUM>).

Probe request frames <NUM> with real MAC addresses (i.e. training probe request frames <NUM>) follow the lower branch <NUM>, and they are used for training at the server <NUM>. Randomized MAC addresses and real MAC addresses are identified using the second less-significant bit of the first byte of the MAC address. In particular, if the second character in a MAC address is a <NUM>, <NUM>, A, or E, then it is a randomized MAC address; otherwise, the MAC address is a real MAC address. For instance, the MAC address <NUM>:B1:B8:<NUM>:D1:<NUM> is a randomized MAC address because the second character is a <NUM>. In the lower branch <NUM> the fingerprints are also calculated from training probe request frames <NUM> that contain real MAC addresses of Wi-Fi devices, but the fingerprints are not needed to determine how many MAC addresses mask a single device since one real MAC corresponds to one Wi-Fi device. For the same reason, in this training process it is also not necessary to separate clusters within a fingerprint from probe request frames with real MAC addresses (the post-processing step <NUM> is not required). However, the processing of probe request frames with real MAC addresses allows to take advantage of the fact that the number of real devices is known, in order to calibrate some system parameters. Indeed, the training system can obtain an output and, knowing what the correct output should be, the system can adapt some values or parameters to match both results (output vs expected output).

This process is known as model training <NUM>, which is performed at the server <NUM>, and the results are the estimated best values for the learned parameters, namely the temporal span <NUM> of the time window (the time duration of the analysis window) and/or the clustering threshold <NUM> (threshold for maximum distance within a single cluster, threshold of the maximum distance from which we consider that it is not only a single cluster, but two clusters). These values will be different in each scenario or installation <NUM>. In other words, the values will not be the same for deployment in a shopping centre, a school, or a beach, for instance. With this training process, the system can constantly self-calibrate (although after some time of operation, these parameters shall remain stable).

According to an embodiment, the training process groups all the real-MAC aggregated bursts <NUM> by its MAC address using time windows with different temporal spans <NUM> and finds the average spread scoring <NUM> of the aggregated bursts <NUM> of the same Wi-Fi device for each temporal span. The trained temporal span <NUM> may be selected, for instance, according to the following process:.

Claim 1:
A method of identifying Wi-Fi devices, the method (<NUM>) comprising:
receiving (<NUM>), by a plurality N of access points (AP<NUM>, AP<NUM>,..., APN) arranged at an installation (<NUM>), probe request frames (<NUM>) sent by Wi-Fi devices (<NUM>);
for each probe request frame (<NUM>) received at an access point (AP<NUM>, AP<NUM>,..., APN), generating (<NUM>) a fingerprint (<NUM>) from a set of features extracted from a plurality of fields of the probe request frame (<NUM>);
sending (<NUM>), from the plurality N of access points (AP<NUM>, AP<NUM>,..., APN) to a server (<NUM>), the generated fingerprint (<NUM>), a timestamp (<NUM>) and an RSSI measurement (<NUM>) associated to each probe request frame (<NUM>);
the method being characterised in that it comprises:
identifying (<NUM>) for each access point, by the server (<NUM>), bursts (<NUM>) of probe request frames using the timestamps (<NUM>), each burst (<NUM>) being a group of probe request frames with the same source MAC address received by the access point in a configurable span of time;
for each burst i (<NUM>) of probe request frames, determining (<NUM>) an average RSSI measurement xij (<NUM>) by averaging the RSSI measurements associated with all the probe requests frames of the burst;
grouping the bursts (<NUM>) of probe request frames by their fingerprints (<NUM>) and clustering each group by performing an N-dimensional cluster analysis (<NUM>) on the averaged RSSI measurements xij (<NUM>) received by each access point (AP<NUM>, AP<NUM>,..., APN), obtaining at least one cluster (<NUM>) per fingerprint (<NUM>); and
identifying (<NUM>) a Wi-Fi device for each different cluster (<NUM>).