<  Back to the Polytechnique Montréal portal

Exploitation des protocoles WiFi pour le décompte automatique des personnes aux alentours d'un point donné

Erwan Nisol

Master's thesis (2022)

Open Access document in PolyPublie
[img]
Preview
Open Access to the full text of this document
Terms of Use: All rights reserved
Download (1MB)
Show abstract
Hide abstract

Abstract

In cities around the world, the public transportation sector plays a pivotal role in the daily lives of many. Understanding the behaviour of a city's ridership in real-time is essential to reduce its operating costs and enhance passenger satisfaction. Bus systems, specifically, are notorious for extended waiting times, overcrowding and ineffective routes. Data collected based on passenger behaviour allows for greater flexibility in bus scheduling and helps reduce the burden of single passengers on the overall transport network. A solution for assessing travel demand in real-time is to count the number of people waiting at each bus stop to forecast future load on the system. Mainly motivated by these considerations, this thesis proposes an approach using WiFi communication protocols to estimate the number of connected devices present around a given point. In the past, WiFi-based methods were made easier by the existence of a unique identifier called "Media Access Control" (MAC) address which was systematically transmitted by connected devices to discover access providers surrounding them. Since 2013, the use of a randomized MAC address has become more widespread making tracking and counting devices much harder. Fortunately, previous work from Vanhoef et. al in 2016 has shown that this randomization process is not enough to prevent tracking. In their article, the authors introduced a clustering algorithm they claim capable of tracking perfectly 50% of devices over a span of 20 minutes. In 2020, another clustering algorithm called DBSCAN used by Uras et al. was able to count the number of devices with an accuracy of 65.2%. In this thesis, a metric learning and Bayesian modeling is proposed to improve the existing literature. A maximum likelihood estimator is built on the calculated clusters and assigned a confidence interval. Experimental results on the public WiFi dataset, CRAWDAD, has shown that the proposed method achieves a relative error of 21% using each clustering algorithm, without access to the MAC address.

Résumé

La ville moderne est sans cesse confrontée à de nombreux défis. Parmi eux figurent notamment son accessibilité en transports et la satisfaction de ses usagers rendues de plus en plus difficile par un nombre grandissant de contraintes. En effet, en plus des limites financières, il est aujourd'hui impossible d'ignorer l'impact environnemental des transports en commun dans la situation actuelle de crise climatique. Une meilleure compréhension du comportement des utilisateurs des autobus est critique pour permettre plus d'optimisations du réseau de transports. Par exemple, la connaissance en temps réel du nombre de personnes patientant à chaque arrêt de bus pourrait mener à l'émergence de transports en commun plus flexibles et moins coûteux. Principalement motivés par cette problématique, nous proposons une méthode de comptage d'appareils connectés présents autour d'un point donné exploitant les protocoles de communication WiFi. Antérieurement à 2013, les appareils connectés commu-niquaient systématiquement un identifiant unique appelé adresse MAC lorsqu'ils sondaient leurs alentours à la recherche de fournisseurs d'accès, dans des paquets de données appelés "Requêtes de Sonde". Cela rendait alors le décompte de ces appareils aisé. Cependant, depuis 2013, ce décompte a été rendu difficile par l'introduction de l'utilisation quasi-systématique d'une fausse adresse MAC aléatoire. Dans ce mémoire, nous avons mis au point une approche fondée sur l'apprentissage d'une métrique adaptée à l'espace des Requêtes de Sonde. Cette métrique est ensuite exploitée dans un algorithme de partitionnement. Un estimateur du maximum de vraisemblance est ensuite utilisé pour prédire le nombre d'appareils et établir un intervalle de confiance. Les résultats expérimentaux menés sur les données WiFi publiques de CRAWDAD montrent que notre méthode atteint une erreur relative de 21%, et ce sans accéder à l'adresse MAC.

Department: Department of Mathematics and Industrial Engineering
Program: Maîtrise recherche en mathématiques appliquées
Academic/Research Directors: Richard Labib
PolyPublie URL: https://publications.polymtl.ca/10555/
Institution: Polytechnique Montréal
Date Deposited: 06 Feb 2023 15:01
Last Modified: 07 Feb 2024 05:22
Cite in APA 7: Nisol, E. (2022). Exploitation des protocoles WiFi pour le décompte automatique des personnes aux alentours d'un point donné [Master's thesis, Polytechnique Montréal]. PolyPublie. https://publications.polymtl.ca/10555/

Statistics

Total downloads

Downloads per month in the last year

Origin of downloads

Repository Staff Only

View Item View Item