🤖 AI

Graph-Based Floor Separation Using Node Embeddings and Clustering of WiFi Trajectories

Questo articolo presenta un framework basato su grafi, completamente guidato dai dati, che realizza la separazione cieca dei piani verticali in edifici multipiano modellando le traiettorie dei fingerprint Wi-Fi come nodi, apprendendo embedding strutturali tramite Node2Vec e applicando il clustering K-Means con stima automatica dei cluster, il tutto senza richiedere metadati edilizi preventivi.

Autori originali: Rabia Yasa Kostas, Kahraman Kostas

Pubblicato 2026-02-03

📖 4 min di lettura☕ Lettura da pausa caffè

CC BY 4.0

Autori originali: Rabia Yasa Kostas, Kahraman Kostas

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di camminare attraverso un enorme centro commerciale su più piani. Non hai segnale GPS, non hai una mappa e non sai nemmeno a che piano ti trovi. I segnali Wi-Fi che rimbalzano sulle pareti e sui mobili sembrano quasi identici, sia che tu sia al 3° che al 4° piano. Questo è il problema della "localizzazione verticale": capire a che piano ti trovi solo ascoltando i segnali Wi-Fi.

Questo articolo propone un modo intelligente e basato sui dati per risolvere questo enigma senza bisogno di una planimetria dell'edificio o di sapere quanti piani esistono in precedenza. Ecco come hanno fatto, spiegato in modo semplice:

1. Il Problema: La "Zuppa di Segnali"

Negli edifici grandi, i segnali Wi-Fi sono disordinati. Filtrano attraverso i pavimenti, rimbalzano sulle vetrate dei grandi atri e si confondono con i mobili. Se guardi solo la forza del segnale in un singolo momento, è come cercare di indovinare in quale stanza di una casa ti trovi annusando una singola goccia di caffè; è troppo vago.

2. La Soluzione: Trasformare i Segnali in un "Social Network"

Invece di guardare i segoli uno alla volta, gli autori trattano l'intero percorso come un social network.

I Nodi (Le Persone): Ogni volta che il telefono registra un segnale Wi-Fi, è come una persona a una festa.
Gli Archi (Le Amicizie): Se sei passato da un punto a un altro, quei due segnali sono "amici". Se due segnali sono molto simili (anche se non ci sei passato tra di loro), sono comunque "amici".

Collegando tutti questi segnali, costruiscono una gigantesca mappa di amicizie (un grafo).

3. Il Trucco Magico: "Imparare l'Atmosfera" (Node2Vec)

Una volta ottenuta questa gigantesca mappa, utilizzano una tecnica chiamata Node2Vec. Immagina questo come un detective che gira per la festa, osservando chi frequenta chi.

Invece di guardare solo chi sta vicino a chi, il detective impara l' "atmosfera" di diversi gruppi.
Le persone al 3° piano potrebbero frequentare un cerchio specifico, mentre le persone al 4° piano ne frequentano un altro, anche se la stanza sembra la stessa.
L'algoritmo trasforma questi complessi cerchi sociali in semplici "tessere d'identità" (vettori) che catturano l'essenza di quel piano.

4. Raggruppare gli Indizi (Clustering)

Una volta che tutti hanno una "tessera d'identità", il computer utilizza uno strumento di ordinamento semplice (K-Means) per raggruppare le persone che hanno tessere d'identità simili.

Il Risultato: Tutte le "persone del 3° piano" finiscono in un mucchio, e tutte le "persone del 4° piano" in un altro.
La Parte Interessante: Il computer capisce automaticamente quanti mucchi ci sono. Non deve essergli detto: "Ci sono 5 piani". Semplicemente osserva i dati e dice: "Ah, vedo 5 gruppi distinti".

5. Il Test: Ha Funzionato?

Gli autori hanno testato il loro metodo su due diversi dataset del mondo reale (uno proveniente da una sfida universitaria e uno da un famoso benchmark di ricerca).

Il Confronto: Hanno messo il loro metodo contro i metodi tradizionali più vecchi per ordinare i dati (come il semplice raggruppamento o le complesse reti neurali).
L'Esito: Il loro metodo è stato il vincitore netto.
- Sul dataset rumoroso e difficile, il loro metodo ha ottenuto circa il 76% di precisione, mentre il secondo miglior metodo otteneva solo il 50%.
- Sull'altro dataset, il loro metodo ha performato altrettanto bene come se avessero utilizzato misurazioni fisiche perfette (come conoscere l'altezza esatta di ogni punto), nonostante abbiano usato solo i segnali Wi-Fi.

6. Perché è Speciale

Nessuna Planimetria Necessaria: Non serve conoscere la disposizione dell'edificio o quanti piani ha. Il sistema lo capisce da solo.
Nessun Sensore Extra: Non ha bisogno di barometri (sensori di pressione) o accelerometri; usa solo i segnali Wi-Fi già presenti sul tuo telefono.
Robustezza: Anche quando i segnali Wi-Fi sono disordinati e l'edificio ha spazi insoliti (come un grande atrio aperto), questo approccio a "social network" riesce comunque a separare correttamente i piani.

In breve: Gli autori hanno trasformato un disordinato mucchio di segnali Wi-Fi in un social network, hanno lasciato che un'IA imparasse la "personalità" di ogni piano e poi li hanno divisi in gruppi. È un modo per capire a che piano ti trovi solo ascoltando il Wi-Fi, senza mai aver bisogno di una mappa.

Sintesi Tecnica: Separazione dei Piani Basata su Grafi Utilizzando Node Embedding e Clustering di Traiettorie Wi-Fi

Definizione del Problema
La localizzazione verticale, specificamente la separazione dei piani in ambienti interni multi-piano, rimane una sfida significativa per i Sistemi di Posizionamento Indoor (IPS). A differenza dei sistemi GPS esterni, gli ambienti interni soffrono di ostruzioni del segnale, interferenze da multipath e perdite di segnale tra i piani (particolarmente in atrii e spazi aperti), portando a pattern di segnale sovrapposti. I metodi tradizionali di fingerprinting Wi-Fi si affidano spesso all'apprendimento supervisionato, che richiede estesi dati etichettati e conoscenze pregresse dell'edificio (ad esempio, planimetrie o numero di piani). Le soluzioni dipendenti dall'hardware (barometri, IMU) affrontano problemi di deriva della calibrazione e scalabilità. Questo articolo affronta la necessità di un approccio completamente data-driven e non supervisionato per la separazione cieca dei piani che non richieda informazioni pregresse sull'edificio, non richieda la conoscenza del numero di piani e si basi esclusivamente sulle traiettorie RSSI (Received Signal Strength Indicator) del Wi-Fi.

Metodologia
Il framework proposto formula la separazione dei piani come un problema di clustering di grafi non supervisionato. La metodologia procede attraverso le seguenti fasi:

Costruzione del Grafo:
- Nodi: Ogni fingerprint Wi-Fi (un vettore di valori RSSI da Access Point visibili) è rappresentato come un nodo.
- Archi: Gli archi catturano sia la somiglianza del segnale che il contesto di movimento sequenziale.
  - Archi Orizzontali: Connettono fingerprint sequenziali all'interno della stessa traiettoria dell'utente per preservare la continuità temporale.
  - Archi Verticali/Sintetici: Nei dataset privi di etichette esplicite di transizione verticale (ad esempio, UJIIndoorLoc), vengono introdotti archi sintetici esclusivamente per garantire che il grafo rimanga una singola componente connessa, senza codificare l'identità del piano o la supervisione verticale.
- Pesatura degli Archi: I pesi rappresentano la prossimità tra i fingerprint. Lo studio valuta tre strategie:
  - Default: Stime di distanza rumorose fornite dai dataset delle competizioni.
  - WBDE (Wi-Fi-Based Distance Estimation): Distanze ricalcolate utilizzando un modello di ML supervisionato addestrato su dataset di posizionamento orizzontale esterni (garantendo l'assenza di data leakage dal compito di classificazione del piano).
  - Geometric Gold Standard: Distanze euclidee derivate dalle coordinate reali (utilizzate solo per UJIIndoorLoc come limite teorico superiore).
Node Embedding:
- Il framework utilizza Node2Vec per apprendere embedding vettoriali a bassa dimensionalità ( $d=32$ ) dei nodi. Node2Vec utilizza random walk distorti per bilanciare la ricerca Depth-First Search (DFS) e Breadth-First Search (BFS), catturando sia l'omofilia locale che l'equivalenza strutturale globale.
- Lo studio confronta anche il metodo con le Graph Neural Networks (GCN e GAT), sebbene queste dipendano da un'esplicita aggregazione di feature che può essere soggetta a over-smoothing in grafi Wi-Fi rumorosi.
Clustering e Stima:
- Gli embedding appresi vengono raggruppati utilizzando K-Means.
- Stima Automatica dei Cluster: Per determinare il numero di piani ( $k$ ) senza conoscenza preventiva, il sistema utilizza l'Indice di Calinski-Harabasz (CH). L'algoritmo valuta iterativamente $k$ all'interno di un intervallo [3, 20] (basato sui vincoli della Huawei Challenge) e seleziona il $k$ che massimizza il rapporto tra dispersione inter-cluster e intra-cluster.
Valutazione:
- Poiché il metodo è non supervisionato, uno schema di maggioranza post-hoc mappa i cluster anonimi ai label fisici dei piani per il calcolo delle metriche.
- Le prestazioni sono misurate utilizzando Mapped Accuracy, Weighted F1-Score, Adjusted Rand Index (ARI), Normalized Mutual Information (NMI) e Cluster Purity.
- La robustezza statistica è garantita tramite 1.000 iterazioni di bootstrap.

Dataset
Il framework è valutato su due dataset distinti:

Huawei University Challenge 2021: Un dataset su larga scala con traiettorie di cammino continue e stime di distanza rumorose.
UJIIndoorLoc: Un dataset benchmark che copre tre edifici. Gli autori hanno ristrutturato questo dataset per generare traiettorie da fingerprint discreti, trattando i subset di Training e Validation come esperimenti indipendenti per testare la generalizzabilità.

Risultati Chiave

Superiorità rispetto ai Baseline: La pipeline proposta Node2Vec + K-Means ha superato significativamente gli algoritmi tradizionali di community detection (Louvain, Leiden, Infomap, Label Propagation, Fast Greedy) e i modelli GNN (GCN, GAT).
- Sul dataset Huawei (usando distanze WBDE), il metodo proposto ha raggiunto il 76,60% di accuratezza (95% CI [0,739, 0,806]), battendo decisamente il miglior baseline (GAT al 50,2%).
- Sul dataset UJIIndoorLoc, il metodo ha raggiunto il 66,1% di accuratezza sul subset di Training e il 59,4% sul subset di Validation, superando sostanzialmente i baseline che spesso scendevano sotto il 25% nel subset di Validation.
Impatto della Stima della Distanza: Sostituire le distanze default rumorose con stime basate su WBDE ha migliorato significamente le prestazioni (dal 69,3% al 76,6% su Huawei), confermando che una topologia di grafo più pulita è critica per il clustering.
Equivalenza alla Geometria: Una scoperta fondamentale è che, sul dataset UJIIndoorLoc, le prestazioni di clustering utilizzando distanze derivate puramente dal segnale (WBDE) erano statisticamente indistinguibili dai risultati del "Gold Standard" ottenuti con distanze geometriche reali. Ciò suggerisce che il metodo può recuperare la disposizione strutturale fisica esclusivamente dai dati RSSI.
Integrità Strutturale: Mentre gli algoritmi tradizionali raggiungevano un'alta Cluster Purity (spesso >90%), soffrivano di una grave over-segmentazione (ARI vicino allo zero), fallendo nell'identificare comunità coerenti a livello di piano. L'approccio Node2Vec ha mantenuto alti punteggi ARI (ad esempio, 0,669 su Huawei), indicando che cattura con successo la coerenza strutturale globale.

Significatività e Claim
L'articolo sostiene che il suo contributo principale sia una soluzione scalabile e indipendente dall'hardware per la localizzazione verticale che elimina la dipendenza da metadati specifici dell'edificio o da dati di addestramento etichettati.

Capacità Non Supervisionata: Il metodo esegue con successo la separazione cieca dei piani, stimando il numero di piani e partizionando le traiettorie senza conoscenza preventiva della disposizione dell'edificio.
Robustezza al Rumore: Sfruttando l'apprendimento di rappresentazioni grafiche (Node2Vec) invece dell'aggregazione diretta delle feature (GNN) o dell'ottimizzazione della modularità locale, il framework è robusto all'alto rumore e alle fluttuazioni del segnale inerenti agli ambienti Wi-Fi.
Generalizzabilità: L'approccio dimostra prestazioni consistenti attraverso diverse scale architettoniche e metodologie di raccolta dati (traiettorie continue vs. fingerprint discreti ricostruiti).
Praticità: Il framework si basa solo su dati di fingerprint Wi-Fi standard, rendendolo applicabile alle infrastrutture wireless esistenti senza richiedere sensori aggiuntivi (come barometri) o calibrazioni complesse.

Gli autori concludono che, sebbene la qualità della stima della distanza (tramite WBDE) migliori le prestazioni, il valore centrale risiede nella capacità del framework basato su embedding di recuperare autonomamente la disposizione strutturale di edifici multi-piano partendo esclusivamente da dati di segnale rumorosi.