Un oracolo per la scelta location-based dell'interfaccia di rete nei dispositivi mobili

(1)

Alma Mater Studiorum · Universit`

a di

Bologna

SCUOLA DI SCIENZE Corso di Laurea in Informatica

Un Oracolo per la scelta

location-based dell’interfaccia di rete

nei dispositivi mobili

Tesi di Laurea in Reti di Calcolatori

Relatore:

Chiar.mo Prof.

Vittorio Ghini

Presentata da:

Michele Corazza

Sessione 2

Anno Accademico 2012-13

(2)

(3)

Introduzione

Questa tesi si pone come obiettivo l’implementazione di uno strumento (l’oracolo) che riesca a discriminare quali interfacce di rete (UMTS/3G o Wi-Fi) mantenere attive, a partire dalle informazioni sulla posizione geografica del dispositivo. Lo studio di tale soluzione trova le sue ragioni negli svilup-pi degli ultimi anni, che hanno reso possibile l’utilizzo di veri e propri PC con dimensioni fortemente ridotte, i dispositivi mobili. Oltre a tale svilup-po, sono sempre più diffuse le reti wireless, come le reti WiFi e 3G, grazie alle quali è possibile avere accesso ad internet in aree sempre più estese e persino all’aperto. È in questo contesto che è stato proposto un approccio per uno switch seamless, invisibile al livello applicativo, fra tipologie di reti eterogenee, denominato Always Best Package Switching (ABPS) [1].

D’altro canto, seppure si siano fatti dei progressi nella riduzione dei consu-mi energetici delle componenti hardware dei dispositivi mobili e nella capacità delle batterie, essi hanno un’autonomia limitata e l’aumento dell’autonomia è un aspetto chiave per l’utilizzo di tali dispositivi. La tecnologia ABPS ha purtroppo dei costi energetici elevati, in quanto trasmette su entrambe le in-terfacce presenti sul dispositivo, aumentandone i consumi. È stato per questo proposto un oracolo che utilizzi le informazioni geografiche, che sono accessi-bili ai dispositivi moaccessi-bili moderni mediante un ricevitore GPS, per limitare i consumi del dispositivo, mantenendo accese solo le interfacce necessarie per garantire la continuità della connessione.

Seppure esistano strumenti simili all’oracolo qui proposto, essi si basano su una fase di apprendimento, che determina quali interfacce siano utili in un

(4)

ii INTRODUZIONE

dato momento. L’oracolo qui proposto, invece, necessita solo in parte di un periodo di training, in quanto sfrutta un database di Access Point(AP) WiFi preesistente, estrapolando da esso le informazioni necessarie a compiere le scelte più appropriate. Esso utilizza inoltre un approccio per la valutazione quantitativa della disponibilità di connettività WiFi, basato su una misura del rapporto fra la superficie in cui è disponibile il segnale e un orizzonte spaziale che circonda il dispositivo.

L’implementazione di tale oracolo è dunque l’oggetto di studio di questa tesi, nella quale analizzeremo dapprima le tendenze e lo scenario di utilizzo che hanno portato alla creazione del software, quali lo sviluppo di reti Wi-Fi e dispositivi mobili. Si specificheranno poi gli obiettivi e le priorità del progetto rispetto ai consumi, alla disponibilità di connessione e al compor-tamento desiderato rispetto agli eventi possibili. Verranno poi specificati gli strumenti utilizzati,quali il sistema operativo Linux e una serie di librerie, nonché le ragioni per il loro utilizzo qualora necessario. Si passerà dunque a descrivere le componenti fondamentali necessarie all’oracolo e il processo di progettazione che ha condotto alla loro realizzazione. Verranno poi de-scritte e motivate alcune scelte implementative significative che realizzano le finalità individuate in fase di progettazione. Infine, verranno fornite delle valutazioni sulla validità dell’approccio adottato, sia tramite un analisi del-le probdel-lematicità relative all’implementazione proposta, sia tramite test per valutar l’efficienza dell’oracolo.

(5)

Indice

Introduzione i

1 Scenario 1

1.1 ABPS e la proposta dell’oracolo . . . 1

1.2 I dispositivi mobili . . . 2

1.3 Le reti mobili . . . 3

1.4 Le reti WiFi pubbliche . . . 4

2 Obiettivi 7 2.1 Effetti desiderati . . . 7

2.2 La scelta: priorit`a e modalit`a . . . 8

2.3 La disponibilit`a del WiFi . . . 9

3 Strumenti e tecnologie utilizzate 11 3.1 Il sistema operativo . . . 11

3.2 Una fonte di informazioni sugli AP: WiGLE . . . 12

3.3 Le librerie C . . . 13

3.3.1 Richieste HTTP e cookie: libcURL . . . 13

3.3.2 Comunicazione con il ricevitore GPS: libgps . . . 14

3.3.3 Informazioni dalla NIC WiFi:iwlib . . . 14

3.3.4 La base di dati: sqlite . . . 14

3.3.5 Linked list: cpan . . . 15

3.3.6 Gli stumenti di testing . . . 15 iii

(6)

iv INDICE

4 Progettazione 17

4.1 Panoramica . . . 17

4.2 Stimare la disponibilit`a . . . 18

4.3 Stimare la portata degli AP . . . 19

4.4 Tables del database e query . . . 22

5 Implementazione 23 5.1 I cambiamenti di stato . . . 23

5.2 Il calcolo dell’area coperta da segnale . . . 24

5.3 Le operazioni di geometria sferica . . . 27

5.3.1 Distanza fra punti: la Great Circle Distance . . . 27

5.3.2 Determinare lo stato dei (sotto)quadrati . . . 28

5.4 La qualit`a del segnale WiFi . . . 30

5.5 Aggiornamenti del database . . . 30

5.6 Costanti e scelte implementative . . . 31

6 Valutazione e sviluppi futuri 33 6.1 Considerazioni preliminari . . . 33

6.2 Problematicit`a . . . 34

6.2.1 La precisione della stima di disponibilit`a . . . 34

6.2.2 L’oracolo e i consumi . . . 35

6.2.3 WiGLE e i dati sugli AP Wifi . . . 37

6.3 I test . . . 38

6.3.1 Test con gpsfake . . . 38

6.3.2 Test con ricevitore GPS . . . 40

6.4 Sviluppi futuri . . . 40

6.4.1 Un’altra fonte di dati per effettuare scelte . . . 40

6.4.2 Migliorare la gestione del WiFi . . . 41

6.4.3 La gestione delle NIC . . . 42

7 Conclusioni 43

(7)

Elenco delle figure

1.1 Consumo delle varie interfacce di rete mobili . . . 4 1.2 AP di Iperbole a Bologna . . . 5 5.1 Intersezione di cerchi . . . 25 5.2 Visualizzazione dell’approccio dei sotto-quadrati utilizzato per

calcolare l’unione fra aree di cerchi . . . 26 6.1 Consumi di una scansione WiFi . . . 36 6.2 Test con gpsfake . . . 39

(8)

(9)

Elenco delle tabelle

1.1 Quote di mercato per classe di dispositivi . . . 3

(10)

(11)

Elenco degli Algoritmi

4.1 Eventi e azioni dell’oracolo . . . 18 5.1 Implementazione dello switch fra stati . . . 24

(12)

(13)

Capitolo 1

Scenario

In questo capitolo affronteremo lo scenario in cui è stato affrontato lo studio dell’oracolo, in particolare rispetto alla crescita dispositivi mobili, alla disponibilità crescente di reti WiFi pubbliche. Si discuterà inoltre di ABPS, poiché la proposta e gli obiettivi dell’oracolo sono derivanti da un articolo, che propone l’utilizzo di un software per ridurre i consumi derivanti da una trasmissione contemporanea di due interfacce di rete.

1.1 ABPS e la proposta dell’oracolo

La proposta di un oracolo in grado di selezionare la Network Interface Card (NIC) più appropriata viene da un articolo [2] nel quale viene proposto un sowftware che selezioni le reti a partire dalle informazioni geografiche. Lo scenario proposto riguarda una tecnologia chiamata ABPS, che consente di mantenere attiva una connessione di rete anche durante il passaggio della connessione fra interfacce diverse. Per effettuare tale operazione, tuttavia, è necessario trasmettere da entrambe le interfacce contemporaneamente, pro-vocando un consumo energetico non trascurabile per i dispositivi mobili. Da ciò deriva la proposta di utilizzare un oracolo, in modo da accendere entrambe le interfacce solo quando si debba passare da un interfaccia all’altra, riducen-do i consumi. Sempre nell’articolo viene proposto un modello per valutare

(14)

2 1. Scenario

tale approccio basato sulle catene di Markov, che mostra come i consumi del sistema ABPS coadiuvato da un oracolo siano ridotti in modo significativo e non vi siano effetti collaterali sulla disponibilit`a di connessione. Sebbene sia questo lo scenario fondamentale per lo studio dell’oracolo proposto, vi sono altre ragioni che rendono un tale software interessante, quali la diffusione di reti WiFi e dei dispositivi mobili.

1.2 I dispositivi mobili

Negli ultimi anni si è assistito a una crescente diffusione di dispositivi mobili per l’utilizzo quotidiano. Tali dispositivi, sempre più potenti, sono ormai dei veri e propri Personal Computer, in grado non solo di offrire una piattaforma per il consumo di contenuti multimediali di vario tipo, ma anche di fornire funzioni un tempo esclusive ai PC tradizionali, grazie a una potenza di calcolo sempre crescente. Secondo i dati forniti da IDC (si veda tabella 1.1) la vendita di smartphone e tablet sorpassa ormai quelle di PC desktop e portatili combinate, rendendo i dispositivi mobili le piattaforme di computing di maggior successo degli ultimi anni. Tali dispositivi dispongono di hardware che spesso non è presente nei pc tradizionali, quali interfacce 2G/3G per l’utilizzo di reti telefoniche e scambio di dati a pacchetto, un ricevitore GPS e altri sensori di varia natura. La presenza di tali sensori, oltre a fornire nuovi paradigmi di interazione uomo/macchina, può essere sfruttata per ottenere informazioni sull’ambiente circostante, aspetto che può essere utilizzato per automatizzare scelte o operazioni sulla base della locazione geografica o di altri fattori quali pressione, temperatura, orientamento del dispositivo, etc. `

E grazie a questi ed altri aspetti che `e stata possibile l’implementazione dell’oracolo oggetto di questa Tesi, che utilizza le informazioni geografiche come dato fondamentale.

(15)

1.3 Le reti mobili 3

T ipo di dispositivo 2012(dati) 2013(stima) 2014(stima) PC (Desktop e Portatili) 341, 273 305, 178 289, 239 Ultramobile 9, 787 20, 301 39, 824 Tablet 120, 203 201, 825 276, 178 Telefonini e smartphone 1.746.177 1.821.193 1901, 188

Tabella 1.1: Quote di mercato per classe di dispositivi. [3]

1.3 Le reti mobili

Parallelamente alla diffusione dei dispositivi mobili, anche prima che essi si trasformassero in PC veri e propri, è nata l’esigenza di costruire reti per lo scambio di pacchetti che fossero adatte all’utilizzo in un contesto di mobilità. Con l’avvento degli smartphone tale sviluppo è accelerato, per far fronte alla necessità di connessione da parte di una sempre maggiore quantità di utenti che utilizzano dispositivi mobili. Se le prime reti GPRS/EDGE fornivano velocità dell’ordine della decina di Kbps, le prime reti 3g/UMTS hano por-tato a velocità dell’ordine del centinaio di Kbps, sufficienti per la fruizione di contenuti testuali e di immagini sul web. Più recentemente le reti HDSPA hanno portato la velocità di trasmissione teorica al Mbps, rendendo possibi-le per gli utenti dai dispositivi mobili il consumo di contenuti multimediali. L’asticella tecnologica è stata ulteriormente alzata con l’avvento delle tecno-logie 4G/LTE, che permettono velocità teoriche dell’ordine del centinaio di Mbps, rendendo di fatto la tecnologia superiore alle ADSL che utilizzano un doppino telefonico per la trasmissione.

Tuttavia questa crescita delle velocità di trasmissione ha un prezzo. Con tale crescita aumentano anche i consumi della Network Interface Card(NIC) associata (figura 1.1). La figura rende evidente come il consumo di un’in-terfaccia 3G e una più tradizionale GSM sia comparabile per alte quantità di dati trasmessi. Tale differenza, tuttavia, diventa più evidente per piccole quantità di dati e quando le interfacce non trasmettono o trasmettono dati

(16)

4 1. Scenario

telefonici o SMS. La figura non riporta i consumi delle NIC 4G/LTE, che non sono oggetto di studio per l’oracolo, ma hanno consumi energetici maggiori di 3G e di WiFi, seppure presentino un consumo per quantità di dati minore rispetto al 3G al crescere della quantità di dati trasmessi [5]. A differenza di un’interfaccia WiFi, inoltre, le interfacce GSM e 3G rimangono attive an-che quando non trasmettono né ricevono dati, poiché sono responsabili delle trasmissioni telefoniche tradizionali e non possono pertanto interrompere il collegamento con la rete. Dalla figura è facile notare, inoltre, come un’in-terfaccia WiFi sia più efficiente di qualsiasi interfaccia mobile, 3G o GSM che sia, oltre a fornire stati di powersave ben codificati che ne minimizzano i consumi quando non viene utilizzata. È quindi sempre preferibile utilizza-re una utilizza-rete WiFi quando essa sia disponibile, spegnendo l’interfaccia 3G ed affidando per lo scambio di chiamate telefoniche ed SMS all’interfaccia 2G.

Figura 1.1: Il consumo delle interfacce di rete GSM, 3G e WiFi. [4]

1.4 Le reti WiFi pubbliche

Oltre al suddetto sviluppo di reti cellulari per la trasmissione di dati, la crescente diffusione di dispositivi mobili ha portato, nelle aree urbane, alla creazione di AP WiFi pubblicamente accessibili, sia offerti da istituzioni pub-bliche, sia da commercianti, hotel e in generale enti privati. Tali AP consen-tono, di solito previa una registrazione, di accedere alla rete anche all’aperto

(17)

1.4 Le reti WiFi pubbliche 5

senza alcun costo. Esempi di tali reti sono presenti nei maggiori aeropor-ti, nelle biblioteche, nelle sedi universitarie. Per quanto riguarda la città di Bologna, ad esempio, esistono due reti fornite rispettivamente dal Comune e dall’Università, che consentono l’accesso ai cittadini registrati, coprendo grosse porzioni del centro storico. ALMAWIFI, la rete di ateneo, fornisce connettività wireless per gran parte della zona universitaria, da via Zambo-ni fino a porta S.Donato, oltre che al Lazzaretto e nelle vicinanze di varie sedi universitarie dentro e fuori porta. Iperbole, la rete pubblica comunale, copre invece il centro cittadino, piazza Maggiore, piazza Verdi, la Montagno-la, il parco del Cavaticcio, piazza Liber Paradisus, etc (si veda figura 1.2). Il comune offre inoltre la possibilità agli esercizi commerciali di partecipare all’iniziativa aggiungendo un router WiFi che fornisce accesso pubblico in cambio di un contributo monetario, in modo da ampliare ulteriormente la disponibilità della rete nell’area urbana.

Figura 1.2: Gli AP pubblicamente accessibili di Iperbole: in rosso quelli del Comune, in blu quelli dei privati. [6]

Sebbene la situazione bolognese non sia che un esempio, sono sempre di più le città che adottano una strategia al fine di fornire AP pubblici ai cittadini e turisti, rendendo di fatto possibile la connettività wifi su porzioni crescenti del territorio. La legislazione italiana, in particolare, che prevedeva dal 2005 una stretta politica di controllo degli accessi, rendendo di fatto obbligatorio l’assegnamento di un account ad ogni utente autorizzato [7], è

(18)

6 1. Scenario

oggi pi`u lasciva e rende possibili ulteriori sviluppi in tale settore [8]. Oltre a queste iniziative, `e interessante segnalare anche il progetto Fon, nato per condividere la propria connessione WiFi in modo sicuro e senza eccessive ripercussioni sulla banda disponibile tramite un router dedicato.

`

E dunque chiaro come la disponibilità di reti pubblicamente accessibi-li nelle aree urbane sia in costante crescita. Partendo dalle considerazioni della sezione precedente sui consumi delle varie interfacce di rete, è dunque interessante chiedersi se sia necessario mantenere attive tutte le interfacce disponibili o se sia possibile in qualche modo discriminare, sulla base del-la posizione geografica dell’utente, quale interfaccia sia del-la più appropriata. `

E proprio questo l’oggetto di studio di questa Tesi, che fornisce anche una prima implementazione di tale meccanismo.

(19)

Capitolo 2

Obiettivi

In questo capitolo tratteremo gli obiettivi dell’oracolo oggetto di questa Tesi. In generale il software dovr`a essere in grado di scegliere lo stato pi`u appropriato rispetto alle NIC necessarie, in particolare discriminando fra tre stati possibili:

Tutto Acceso : Sia la NIC UMTS che quella WiFi sono accese; WiFi Acceso : Solo la NIC WiFi `e accesa;

UMTS Acceso : Solo la NIC UMTS `e accesa;

2.1 Effetti desiderati

L’oracolo di cui si fornisce un’implementazione ha la finalità di effettuare una scelta fra le NIC disponibili in un contesto di mobilità, valutando la scelta più coerente in considerazione di due principali effetti desiderati:

• Massimizzare la disponibilit`a della connessione; • Minimizzare i consumi delle varie NIC;

`

E da subito chiaro come tali finalit`a siano fondamentalmente in contrasto: tanto pi`u si spengono le interfacce inutilizzate in modo aggressivo, quanto

(20)

8 2. Obiettivi

più si minimizza la disponibilità di connettività in caso di scelte errate e viceversa. Nel contesto mobile è lecito considerare la disponibilità di una qualsivoglia connessione come il fattore più importante, poiché la mancanza di un accesso ad internet ha un effetto immediatamente riscontrabile dall’u-tente, mentre i consumi hanno s`ı ripercussioni sull’utilizzo quotidiano, ma più a lungo termine. Sebbene si desideri ridurre i consumi del device, nel contesto dell’oracolo si è tentato di effettuare scelte quanto più possibile conservative, in modo da minimizzare le disconnessioni causate da scelte errate.

2.2 La scelta: priorit`

a e modalit`

a

Uno dei nodi centrali della ricerca del miglior trade-off fra le finalità suddette è la scelta di priorità data alle NIC, effettuata sulla base di due fattori fondamentali:

• La velocit`a di trasmissione delle NIC;

• I consumi delle NIC.

Per quanto riguarda la velocità di trasmissione, non è purtroppo possibile discriminare in modo efficace le reti cellulari di ultima generazione e le reti WiFi. Se, infatti, le velocità teoriche di entrambe le tecnologie possono essere comparare, non è possibile conoscere a priori la banda disponibile in un dato momento. Un semplice esempio può essere fatto considerando un AP WiFi 802.11n e una rete cellulare HDSPA+. Se la velocità teorica dell’AP (senza considerare interferenze e perdite di pacchetti) raggiungerebbe 600 Mbit/s, non vi è garanzia che la banda in uscita dall’AP non sia anche di molto in-feriore a tale valore, fino a rendere l’AP una scelta svantaggiosa. Viceversa, se la velocità teorica di HDSPA+ è di 168 Mbit/s, gli stessi problemi di ban-da disponibile ed interferenze potrebbero renderla la scelta più svantaggiosa. Pertanto, sebbene vi sia un vantaggio teorico in termini di banda nell’utilizzo di tecnologie WiFi, la scelta non può essere fondata su tale fattore, troppo

(21)

2.3 La disponibilit`a del WiFi 9

dipendente dalla situazione particolare. Per quanto riguarda i consumi, in-vece, la situazione è molto più chiara. Le NIC WiFi sono molto più efficienti dal punto di vista energetico e consentono modalità di standby impossibili alle NIC cellulari.

Per queste considerazioni si è scelto di preferire una connessione WiFi ogni qualvolta essa sia disponibile, utilizzando la NIC cellulare come dispositivo di riserva per garantire connettività in ogni situazione. È inoltre importan-te considerare come, nella maggior parimportan-te dei dispositivi mobili moderni sia possibile far operare la NIC cellulare anche in modalità GSM, riducendo in modo sostanziale i consumi in stato di idle, pur consentendo l’utilizzo della rete telefonica.

2.3 La disponibilit`

a del WiFi

Abbiamo dunque visto come la disponibilità di AP WiFi di cui sia pos-sibile ricevere il segnale sia il parametro più importante per discriminare fra i vari stati possibili. È quindi a partire da tale dato che si effettua la scelta sullo stato selezionato, tenendo conto delle priorità discusse in precedenza. Pertanto è auspicabile accendere la NIC WiFi ogni qual volta sia disponibile un AP nelle vicinanze, eventualmente mantenendo accesa la NIC UMTS in caso di dubbio, e spegnere la prima interfaccia solo in caso di assenza di segnale. Per effettuare tale scelta è necessario valutare la disponibilità di connettività WiFi in un dato momento. Tale valore, però, è conoscibile a priori solamente attivando la NIC associata e compiendo una scansione delle reti disponibili. È a questo punto, tuttavia, che ci viene in aiuto la presenza di un ricevitore GPS sul dispositivo. Tramite tale ricevitore, infatti, è pos-sibile, conoscendo gli AP di una data zona, effettuare una valutazione sulla disponibilità della connessione. Tale valutazione, però, non può però sempli-cemente considerare ogni AP disponibile in loco, in quanto la maggior parte di essi è protetta da chiave di cifratura non in nostro possesso.

(22)

10 2. Obiettivi

dipende da molti fattori, la maggior parte dei quali non `e possibile conoscere in modo esaustivo, un problema su cui torneremo in seguito.

Pertanto è indispensabile mantenere un elenco di AP, legati alle proprie posizioni geografiche, alla portata e alla possibilità di connessione. Tale pos-sibilità può dipendere dalla conoscenza dei dati d’accesso, dalla assenza di cifratura o dalla possibilità di accesso pubblico, casi che pertanto devono essere considerati.

Per compilare tale elenco in maniera esaustiva sarebbe necessario trian-golare la posizione e valutare la portata dell’AP durante gli spostamenti. Ci`o porterebbe a un lungo periodo di training, durante il quale l’oracolo non sarebbe in grado di effettuare alcuna scelta sensata e dovrebbe mantenere accese tutte le interfacce disponibili, memorizzando le aree gi`a visitate.

(23)

Capitolo 3

Strumenti e tecnologie

utilizzate

Nel seguente capitolo tratteremo le tecnologie che sono state utilizzate per la creazione. In particolare verranno discusse le necessit`a che hanno portato alla scelta del sistema operativo e delle librerie utilizzate.

3.1 Il sistema operativo

`

E stato già chiarito nei capitoli precedenti come lo scenario di utilizzo per l’oracolo proposto sia nel contesto dei dispositivi mobili. Sarebbe quindi lecito selezionare un sistema operativo comunemente installato su tali dispo-sitivi. Vi sono tuttavia una serie di problematiche che hanno portato a una scelta differente. Se un’implementazione su piattaforma IOS sarebbe stata molto complessa se non impossibile, a causa delle forti restrizioni poste sia sulla possibilità di sviluppo e testing su sistemi operativi ed hardware ar-bitrari, sia sulla facoltà di accendere e spegnere direttamente le interfacce di rete. Per quanto riguarda Android, le cui politiche sono meno restritti-ve riguardo gli aspetti sopra citati, vi è un altro problema. Il software in questione è stato strutturato come un demone, sempre attivo, che pertanto beneficia fortemente di una codifica di basso livello. La libreria bionic,

(24)

12 3. Strumenti e tecnologie utilizzate

mentazione della libreria C di sistema per Android, appare poco utilizzata e la documentazione ad essa associata `e scarsa, per non parlare delle comples-sit`a delle interazioni con service provider quali LocationService per ottenere la posizione geografica.

Si è pertanto di selezionato come sistema operativo per la realizzazione dell’oracolo Linux in senso più tradizionale, utilizzando il linguaggio C e le librerie di sistema GNU. Questo ha portato anche a forti benefici per quanto riguarda la disponibilità di librerie di terze parti per gestire vari aspetti del sistema. Non è da escludere che in futuro vi siano un maggior numero di dispositivi mobili che utilizzano Linux, né la possibilità di un porting su Android.

3.2 Una fonte di informazioni sugli AP:

Wi-GLE

Come esplicitato in precedenza, l’oracolo necessita di una grande mole di informazioni sulla posizione e sullo stato degli AP. Raccogliendo tali dati durante l’utilizzo sarebbero necessari forti tempi di apprendimento, che di fatto renderebbero l’oracolo inutile se il dispositivo si trova in luoghi mai visitati in precedenza. Per ovviare a questo problema si `e cercata una fonte di informazioni da complementare a quelle raccolte a runtime, individuando WiGLE1 come migliore alternativa. Si tratta di un database di AP globale, i cui dati vengono caricati dagli utenti. Il sistema fornisce delle API REST per scaricare e caricare dati, con la possibilit`a di filtrare i risultati sulla base della loro posizione geografica o di altri parametri.

Tali risultati vengono utilizzati dall’oracolo per ottenere pi`u informazio-ni possibili sugli AP circostanti. Fra i dati rilevanti vi sono le informazioinformazio-ni identificative di un AP, le coordinate geografiche e un flag “free”, che indica se la rete sia pubblicamente accessibile. Tali informazioni permettono all’o-racolo di conoscere a priori lo stato dell’area circostante, compiendo scelte

(25)

3.3 Le librerie C 13

anche prima di aver effettuato scansioni e di aver determinato le reti per cui si conoscono le credenziali di accesso. Purtroppo il flag “free” non sempre `e settato correttamente, almeno nelle zone della citt`a di Bologna su cui sono stati effettuati test.

Vi sono però due aspetti di WiGLE che, pur non impedendo il suo uti-lizzo nel contesto dell’oracolo, hanno delle ripercussioni sulla disponibilità del servizio. Le query remote sono disponibili solamente agli utenti registra-ti. Sebbene la registrazione sia gratuita e non abbia alcun prerequisito, è dunque necessario memorizzare un cookie per effettuare richieste al di fuori del browser. Il numero di richieste per utente in un lasso di tempo è inoltre fortemente limitato. Non vi sono indicazioni più specifiche sui limiti imposti agli utenti, ma dopo qualche decina di richieste l’utente viene bannato per un tempo imprecisato, venendo rimandato a una pagina di errore ad ogni richiesta. Discuteremo in seguito come si sia tentato di mitigare l’impatto di tale restrizione. La licenza di utilizzo di WiGLE non permette, infine, di re-distribuire i dati, rendendo impossibile la distribuzione di eventuali database precompilati.

3.3 Le librerie C

In questa sezione descriveremo brevemente le librerie C utilizzate dall’o-racolo e il loro ruolo.

3.3.1 Richieste HTTP e cookie: libcURL

Al fine di semplificare la gestione delle query remote a WiGLE, si è scelto di utilizzare la libreria libcURL, che fornisce, tra le svariate funzioni, un’inter-faccia semplice per effettuare richieste HTTP. In precedenza si è discussa la necessità di utilizzare un cookie di autenticazione per poter accedere ai servizi REST di WiGLE. La libreria libcURL permette il salvataggio e l’utilizzo di cookie in formato Netscape, nonché di settare uno user-agent personalizzato (necessario per effettuare le query a WiGLE).

(26)

14 3. Strumenti e tecnologie utilizzate

3.3.2 Comunicazione con il ricevitore GPS: libgps

Sulle distribuzioni Linux tradizionali `e presente un demone, chiamato gpsd, per fornire ai software che lo richiedono la possibilit`a di accedere ai dati di un ricevitore GPS. Al fine di accedere ai dati forniti dal ricevitore, viene fornita una libreria C chiamata libGPS, in grado di esportare i dati letti dal device in una struttura dati di facile utilizzo.

3.3.3 Informazioni dalla NIC WiFi:iwlib

Sebbene venga fornita un’interfaccia di basso livello per la comunicazione con la NIC WiFi (wireless.h), nell’oracolo si è utilizzata una libreria di più alto livello, chiamata iwlib, che viene fornita con i cosiddetti wireless tools (iwlist, iwconfig, etc). Tali strumenti sono stati recentemente sostituiti dal software iw, che utilizza nuove interfacce per la comunicazione con il kernel. Sebbene l’utilizzo di suddetti software sia scoraggiato poichè fa uso dell’an-tiquata interfaccia Wireless Extension per la comunicazione con il kernel, la libreria ad essi associata permette di semplificare fortemente la richiesta di dati riguardanti l’interfaccia di rete e la scansione delle reti disponibili. Non si era, in un primo momento, reperita un’alternativa valida a iwlib; si è suc-cessivamente trovata una libreria promettente, wapi. Sebbene sia possibile, in prospettiva, sostituire iwlib con wapi. Quest’ultima però fa ancora uso di iwlib per il parsing dei risultati di uno scan. Inoltre, sebbene il feature set sia sufficiente per le necessità dell’oracolo, la libreria appare poco diffusa e le ultime modifiche al codice risalgono al 2010.

3.3.4 La base di dati: sqlite

Per memorizzare i dati relativi agli AP si `e scelto di utilizzare il noto database sqlite, che fornisce convenienti interfacce di programmazione per il linguaggio C tramite la libreria sqlite3. Tale database ha il vantaggio di non richiedere alcuna configurazione e alcun server per le comunicazioni

(27)

3.3 Le librerie C 15

con il database, utilizzando semplici letture-scritture su file direttamente dal processo che ne fa uso.

3.3.5 Linked list: cpan

Al fine di utilizzare linked list con sentinella, si `e scelta una piccola li-breria fornita da CCAN, che fornisce le principali primitive per la scansione, l’aggiunta e la rimozione di nodi, nonch´e per ottenere l’elemento che contiene il nodo della lista, in modo simile a quanto fornito dalle liste di Linux.

3.3.6 Gli stumenti di testing

Al fine di testare le performance del software senza la necessità di reali spostamenti e di un ricevitore GPS, si è scelto di utilizzare gpsfake. Tale software, scritto in python, leggendo file NMEA consente di simulare un ri-cevitore GPS e il demone gpsd ad esso associato, fornendo alle applicazioni informazioni relative alla posizione, al tempo del fix e all’altitudine. Sfortu-natamente tale software non è in grado di rispettare i delta temporali fra le sentence NMEA. Per ovviare a tale problema si è spesso imposto un ritardo fra le sentence NMEA a gpsfake. Ciò può causare l’assenza dell’altitudine nella posizione triangolata o l’assenza di un fix temporale, fatti che hanno imposto una particolare attenzione in alcune porzioni del programma. Al fine di utilizzare un GPS reale si è inoltre usato shareGPS per Android, che consente di utilizzare il ricevitore di uno smartphone e trasmetterne i dati via bluetooth emulando una porta seriale.

Al fine di produrre file NMEA si `e utilizzato routeconverter, un software grafico in grado di produrre un percorso a partire dai punti di partenza ed arrivo su una mappa, esportando i risultati in svariati formati.

Infine, per visualizzare i dati di gpsfake, si `e utilizzato xgps, un’interfaccia grafica per l’utility testuale gpsmon, in grado di stabilire una connessione con gpsd e mostrare i vari parametri da esso esportati, quali posizione, tempo, altitudine, stime degli errori di posizione.

(28)

(29)

Capitolo 4

Progettazione

Segue una descrizione approfondita dei problemi fondamentali coinvolti nella progettazione dell’oracolo, delle soluzioni possibili e di quelle effettiva-mente implementate.

4.1 Panoramica

Occorre innanzitutto individuare la struttura fondamentale dell’oraco-lo, in particolare gli eventi che scatenano un mutamento di stato. Possia-mo immediatamente individuare un algoritPossia-mo che rappresenti la struttura dell’oracolo rispetto al sopraggiungere degli eventi fondamentali:

Se la struttura di base dell’algoritmo è chiara e semplice, bisogna ora considerare come possano essere generati gli eventi sopra descritti. Come abbiamo più volte specificato i dati fondamentali a nostra disposizione ri-guardano la posizione corrente del dispositivo e la posizione di una serie di AP WiFi, reperiti tramite WiGLE. È pertanto necessario studiare delle me-triche che misurino la disponibilità di connettività WiFi nelle vicinanze a partire dalla posizione degli AP.

(30)

18 4. Progettazione

Algorithm 4.1 Eventi e azioni dell’oracolo

1: Upon EV N O W IF I 2: activeW IF I = F ALSE 3: activeU M T S = T RU E 4: 5: Upon EV SHORT W IF I 6: activeW IF I = T RU E 7: activeU M T S = T RU E 8: 9: Upon EV LON G W IF I 10: activeW IF I = T RU E 11: activeU M T S = F ALSE 12:

4.2 Stimare la disponibilit`

a

Durante la progettazione del software si sono cercate delle metriche in grado di dare una stima della disponibilità del WiFi per l’utente. Si sono in questo contesto individuati tre approcci possibili. Il primo approccio prevede una previsione dei successivi spostamenti del device, in particolare conside-rando una posizione stimata nel futuro prossimo, basata sugli spostamenti e sulla lunghezza del ciclo dell’oracolo. Una volta ottenuta tale posizione, è possibile determinare, lungo il percorso fra essa e l’ultima posizione nota, quale sia la disponibilità del WiFi. In particolare, questa quantità è espri-mibile tramite una percentuale, misurando l’intersezione fra il segmento fra i due punti e le zone coperte da WiFi.

Un altro approccio prevede di stimare la percentuale di zone coperte dal segnale WiFi nelle vicinanze del dispositivo, entro una superficie la cui dimensione varia a seconda della velocit`a di spostamento del device.

Un ultimo approccio, indubbiamente il pi`u semplice, prevede di osservare lo stato del segnale nella posizione attuale del dispositivo, non effettuando alcuna previsione.

(31)

4.3 Stimare la portata degli AP 19

Le tre soluzioni proposte hanno problemi e vantaggi le une rispetto alle altre, è pertanto sensato discuterne l’accuratezza e il loro effetto sulla dispo-nibilità di connessione. Nel caso di una scelta basata sulla previsione della posizione futura, si pone il problema di prevedere gli spostamenti, un pro-blema non certo banale. Se esistono approcci basati sul machine learning per risolvere tale problema [9], essi richiedono un tempo di apprendimento, che renderebbe vano l’utilizzo dell’oracolo per lunghi periodi prima di avere risultati sensati. Si potrebbe pensare a un approccio probabilistico, in cui si calcolano la direzione e la velocità media, magari applicando un peso crescen-te ai dati più recenti. Questo approccio tuttavia non da grandi garanzie di precisione. Il terzo approccio, pur essendo molto semplice, non è in grado di stimare le azioni da intraprendere nel futuro e non fornirebbe abbastanza in-formazioni per conoscere la durata della connessione WiFi, non permettendo di discriminare fra gli eventi EV WIFI SHORT ed EV WIFI LONG discus-si in precedenza. Inoltre quando viene intrapresa una scelta il dispodiscus-sitivo potrebbe già essersi mosso ulteriormente, per esempio allontanandosi dalla zona con disponibilità WiFi. La seconda soluzione è probabilmente quella che fornisce il miglior compromesso, tuttavia non è in grado di stimare in mo-do granulare la disponibilità di WiFi, causando effetti negativi sui consumi energetici ma risultando la più conservativa. È stata per questo selezionata quest’ultima come metrica fondamentale per implementare l’oracolo. Scelta una metrica per la disponibilità, resta da risolvere la scelta di un approccio per quantificare la portata del singolo AP, al fine di calcolarne la superficie.

4.3 Stimare la portata degli AP

La stima della portata di un AP `e un problema complesso, che coinvolge sia le caratteristiche degli apparati di trasmissione e ricezione, sia le interfe-renze introdotte da altre sorgenti radio e gli ostacoli presenti fra trasmettitore e ricevente.

(32)

20 4. Progettazione

dello spazio libero, che calcola la perdita di potenza di un segnale attraverso lo spazio, senza considerare le interferenze, i guadagni delle antenne, n´e la presenza di oggetti solidi lungo il percorso:

F SP L = (4πd λ )

2 _(4.1)

Dove:

• FSPL `e la attenuazione dello spazio libero o Free-Space Path Loss; • d `e la distanza fra le due antenne in metri;

• λ `e la lunghezza d’onda del segnale in metri (data dalla frequenza di trasmissione fratto la velocit`a della luce).

Tale formula, tuttavia, non tiene conto della potenza di trasmissione, che invece viene presa in considerazione dal bilancio di collegamento, che `e dato da:

Pr = Pt∗ Gt∗ Gr/(F SP L ∗ L) (4.2)

Dove:

• Pt `e la potenza del segnale trasmesso;

• Pr `e la potenza del segnale ricevuto;

• Gt`e il guadagno dell’antenna del trasmettitore;

• Gr `e il guadagnlo dell’antenna del ricevitore;

• L sono le perdite di segnale;

• F SP L `e la attenuazione di segnale nello spazio libero;

Questa formula, pur non considerando interferenze e ostacoli, non `e di fat-to utilizzabile dall’oracolo, poich´e sono ignoti i guadagni dell’antenna dell’AP e la potenza di trasmissione. Sarebbe possibile invece utilizzare la formula

(33)

4.3 Stimare la portata degli AP 21

applicando valori predefiniti al guadagno dell’antenna e considerando il va-lore di sensibilità della NIC del dispositivo mobile, ma tale approccio non è certo applicabile a un contesto urbano, in cui le barriere architettoniche e le interferenze sono numerose e renderebbero la stima inutile ai nostri scopi. Si potrebbe allora creare una mappa a runtime, rilevando la qualità del segnale ogni qual volta sia possibile. Questo approccio richiederebbe però la cono-scenza dei luoghi prima di poter effettuare stime sensate, rendendo l’oracolo inutile per lunghi periodi di training.

Viste le precedenti considerazioni, si è deciso di approssimare la portata di un AP nel modo seguente: nel caso non si sia visitata l’area coperta dal segnale, si utilizza un valore arbitrario, in caso contrario a runtime si aggiorna un campo del database per stimare la portata massima, considerando una soglia di sicurezza di qualità del segnale per evitare problemi. Mediante queste assunzioni è possibile ridurre la portata dell’AP a una zona circolare che lo circonda, che dipende dalla qualità (non dalla potenza) del segnale nelle zone in cui lo si è osservato.

Questo approccio, che semplifica notevolmente anche le operazioni di cal-colo, può tuttavia creare problemi. Poiché si utilizza la qualità del segnale, che considera anche pacchetti persi e valore di fondo, si potrebbe riscontrare il caso in cui due AP molto vicini trasmettano sullo stesso canale (sulla stessa frequenza) creando forti interferenze nelle loro vicinanze. Il device, passando in una zona in cui le interferenze sono meno forti, aggiornerebbe il valore della portata massima. Nella zona con forti interferenze si avrebbe dunque una stima errata della portata che porterebbe l’oracolo a compiere scelte sba-gliate, per esempio spegnendo l’interfaccia UMTS. La stessa situazione si ha con antenne direzionali, che trasmettono il segnale in modo asimmetrico, per le quali una stima circolare non è applicabile.

(34)

22 4. Progettazione

4.4 Tables del database e query

Vale la pena a questo punto descrivere brevemente la struttura della base di dati utilizata dall’oracolo. Per quanto riguarda gli AP, viene prevista una tabella che contiene le informazioni necessarie alla loro identificazione e geolo-cazione, inclusa la portata massima, che viene aggiornata quando necessario. Poich´e, come evidenziato in precedenza, WiGLE limita fortemente il numero di query effettuabili da uno stesso utente, si devono limitare al massimo le richieste di dati. Per questa ragione il sistema calcola i vertici di una regione quadrata che inscrive un cerchio con raggio di 1000m e centro nella posizione attuale, ottenendo poi da WiGLE gli Ap di tale zona. Al fine di mantenere una traccia delle zone per cui si conoscono i dati, viene memorizzato nel da-tabase un querypoint per ogni richiesta a WiGLE che abbia successo. Tale querypoint contiene la posizione geografica del centro della zona analizzata e un timestamp. Ogni ciclo successivo causer`a una query a WiGLE solo se non vi sono dati nelle vicinanze, altrimenti verranno semplicemente recuperati gli AP necessari dal database.

(35)

Capitolo 5

Implementazione

In questo capitolo tratteremo le scelte implementative pi`u rilevanti nel-l’ambito dell’oracolo.

5.1 I cambiamenti di stato

Abbiamo definito nella fase di progettazione gli eventi che portano a un mutamento di stato dell’oracolo, tuttavia non abbiamo ancora definito quali siano i parametri che vengono utilizzati per rilevare tali situazioni. Tratte-remo anche il comportamento dell’oracolo in alcuni casi particolari, quali la mancanza di segnale GPS o l’impossibilità di ricevere dati da WiGLE. Per discriminare fra i vari stati vengono usate la percentuale dell’area, la qualità e la presenza di un segnale WiFi a cui si è connessi. Viene inoltre incremen-tato un conincremen-tatore, per determinare se si sia connessi a uno stesso AP da molti cicli. La struttura fondamentale dell’oracolo diventa dunque la seguente:

(36)

24 5. Implementazione

Algorithm 5.1 Implementazione dello switch fra stati

1: if status == ALL ON then . Tutte le interfacce accese

2: if covered == 100 OR connected for a while then

3: stauts = W IF I ON

4: end if

5: if covered == 0 AND WiFi not connected then

6: status = U M T S ON 7: end if

8: else if status == W IF I ON then . Solo l’interfaccia WiFi `e accesa

9: if wifi not connected OR covered<100

10: OR signal<theshold then

11: status = ALL ON

12: end if

13: else if status == U M T S ON then . Solo l’interfaccia UMTS `e accesa

14: if covered > 0 then

15: status = ALL ON

16: end if

17: end if

Bisogna inoltre considerare i casi particolari in cui non sia possibile ot-tenere un fix GPS o risposte da WiGLE. In tali casi il sistema si cautela in vari modi: se non si hanno dati sulla posizione, a meno di non essere con-nessi a uno stesso AP da tempo, si preferisce accendere tutte le interfacce, in modo da non causare interruzioni della connessione. Lo stesso approccio si ha in caso di problemi di varia natura nella comunicazione con WiGLE, accendendo tutte le interfacce se non si hanno risultati.

5.2 Il calcolo dell’area coperta da segnale

In precedenza abbiamo esaminato le varie assunzioni che sono state effet-tuate per approssimare l’area con segnale WiFi sufficientemente potente da consentire una connessione. Consideriamo tale area come un cerchio con al

(37)

5.2 Il calcolo dell’area coperta da segnale 25

centro l’AP. A questo punto per ottenere la copertura del segnale è neces-sario calcolare l’area dell’unione dei cerchi. Per effettuare tale operazione è necessario computare le intersezioni fra i cerchi. Se per l’intersezione esclu-siva di n cerchi esistono soluzioni deterministiche quadratiche nel numero di cerchi [11], il problema sorge nel nostro caso, in cui devono essere conside-rate anche tutte le intersezioni non esclusive fra due o più cerchi (si veda figura 5.1). Tale problema non è di semplice soluzione. Un articolo del 2012 sull’argomento [10] fornisce un algoritmo deterministico di complessità espo-nenziale nel numero di cerchi. Tale soluzione non è pertanto applicabile al contesto di un oracolo, che deve minimizzare il suo impatto sulle performance di sistema e che può potenzialmente lavorare su centinaia di cerchi nel caso ci si trovi nelle zone urbane con un gran numero di AP.

Figura 5.1: Intersezione fra cerchi. In rosso le intersezioni esclusive, in giallo quelle non esclusive

Altre soluzioni al problema utilizzano i cosiddetti metodi di Monte Carlo per approssimare la soluzione, di cui il più banale consiste nel utilizzare un certo numero di numeri random e controllare quanti di essi siano inclusi in un cerchio. Tali metodi richiedono un tempo di computazione più ridotto nella dimensione dell’input, mentre il numero di numeri casuali da utilizzare è elevato e cresce all’aumentare dell’area considerata. Oltretutto nel caso di utilizzo di numeri random di buona qualità (es da /dev/random) si avrebbero

(38)

senza dubbio impatti sulla performance del dispositivo, mentre per numeri pseudorandom (es /dev/urandom) sarebbe necessario effettuare il cosiddetto sampling sui numeri pseudorandom ottenuti per garantire la distribuzione numerica richiesta [12].

Si `e scelta pertanto una soluzione che sia in grado di dare un appros-simazione certa del problema ma che risulti di semplice implementazione. Si procede dividendo l’area quadrata in quattro sotto-quadrati uguali. Si determina poi lo stato di ciascun sotto-quadrato rispetto ai cerchi(gli AP):

• Se il quadrato `e interamente contenuto in almeno un cerchio, lo mar-chiamo come pieno;

• Se il quadrato non interseca alcun cerchio, lo marchiamo come vuoto; • Altrimenti, lo marchiamo come sconosciuto.

In questo modo abbiamo una limitazione inferiore della superficie occupata dai cerchi, data dal numero di quadrati marcati come pieni per la loro area. La limitazione superiore è invece data dall’area occupata dai quadrati marcati come vuoti. L’incertezza è infine l’area dei quadrati con stato sconosciuto. Grazie a queste proprietà è possibile selezionare una precisione considerata sufficiente e procedere ricorsivamente dividendo ogni sotto-quadrato con stato sconosciuto fino a raggiungere l’errore desiderato (si veda figura 5.2).

Figura 5.2: Una visualizzazione del metodo utilizzato per approssimare le aree coperte dai cerchi. In nero le aree ”piene“ del quadrato, in grigio quelle con stato incerto. A destra vediamo l’ulteriore suddivisione del quadrato per aumentare la precisione

(39)

5.3 Le operazioni di geometria sferica 27

L’implementazione pratica di tale approccio avviene tramite una parti-colare struttura dati chiamata quadtree, costituita da un albero i cui nodi posseggono esattamente quattro figli. La radice di tale albero `e il quadrato di partenza, i figli sono i sotto-quadrati da esso contenuti. Ogni qual volta si passi al caso ricorsivo il sotto-quadrato viene diviso ulteriormente fino a raggiungere i risultati desiderati.

Si sono effettuati una serie di test nei quali si popolava un’area quadrata con lato di 2000m con mille AP di raggio variabile da 10 a 150 m. Il tempo per calcolare l’area occupata con una confidenza del 3% (su un unico thread di un processore Intel Core i7 con frequenza massima di 3GHz) `e stato inferiore al minuto in tutti i casi. Per contrasto, il metodo deterministico proposto in precedenza avrebbe richiesto O(21000_{) operazioni. Si segnala inoltre come sia}

indubbiamente possibile ottimizzare il processo di calcolo, ad esempio utiliz-zando un approccio parallelo nel quale ogni thread si occupa di scomporre un singolo sotto-quadrato.

5.3 Le operazioni di geometria sferica

Per effettuare i calcoli richiesti dalla misura dell’area descritta in pre-cedenza `e stato necessario implementare una serie di funzioni che compis-sero una serie di operazioni fondamentali sulla superficie terrestre in modo sufficientemente preciso.

5.3.1 Distanza fra punti: la Great Circle Distance

Per calcolare la distanza fra due punti, date le loro latitudini e longitudini, si utilizza una formula detta legge sferica dei coseni:

d = r arccos(sin(φ1) sin(φ2) + cos(φ1) cos(φ2) cos(∆λ)) (5.1)

Dove:

(40)

• φ1, phi2 e λ1, λ2 sono rispettivamente le latitudini e le longitudini dei

due punti

• ∆φ e ∆λ sono i valori assoluti delle differenze fra le latitudini e le longitudini dei due punti

In ambito computazionale, però, vi sono formule che risultano meglio con-dizionate dal punto di vista numerico. Nel contesto dell’oracolo si è scelto di utilizzare un caso particolare della formula di Vincenty, che è un metodo per calcolare le distanze fra punti su un ellissoide, di cui una sfera è un caso particolare:

d = r arctan(p(cos φ2sin ∆λ)

2_{− (cos φ}

1sin φ2 − sin φ1cos φ2cos ∆λ)2

sin φ1sin φ2+ cos φ1cos φ2cos ∆λ

) (5.2) Dove vengono usati gli stessi nomi enunciati in precedenza.

5.3.2 Determinare lo stato dei (sotto)quadrati

Per determinare lo stato di un sotto-quadrato rispetto ad un cerchio bisogna distinguere tre casi:

• Se tutti i vertici del quadrato sono contenuti nel cerchio: il quadrato `e pieno;

• Altrimenti se il cerchio interseca i lati del quadrato o `e contenuto nel quadrato: stato sconosciuto;

• Altrimenti il quadrato `e vuoto.

Il primo caso è dunque di banale verifica, basta applicare la formula per la great circle distance fra i vertici e il centro del cerchio e confrontarla con il raggio del cerchio. Il secondo caso risulta invece più complesso. Poiché il quadrato è costituito da linee di latitudine o di longitudine, per controllare se sia presente un cerchio all’interno del quadrato è sufficiente confrontare le

(41)

5.3 Le operazioni di geometria sferica 29

coordinate del centro con gli estremi di latitudine e longitudine forniti dai segmenti. Per controllare se vi sia intersezione con i lati, occorre invece cal-colare la minima distanza fra i singoli lati e il centro del cerchio e compararla con il raggio. Per effettuare tale operazione si utilizzano due approcci diffe-renti. Nel caso in cui la proiezione del centro del cerchio cada sul segmento, `e sufficiente utilizzare la formula della cross-track distance d:

d = arcsin(sin(dAC/r) ∗ sin(θAC− θBC)) ∗ r (5.3)

Dove:

• A e B sono gli estremi del segmento;

• C `e il punto da cui calcolare la distanza;

• dXY `e la distanza fra i punti X e Y;

• θXY `e l’azimuth iniziale fra i punti X e Y;

Occorre quindi calcolare anche l’azimuth θ12, ovvero la direzione iniziale

in un percorso fra due punti rispetto al nord magnetico:

θ12= arctan(

sin ∆λ cos φ2

cos φ1sin φ2− sin φ1cos φ2cos ∆λ

) (5.4) Dove:

• φ1,2 e λ1,2 sono le latitudini e le longitudini dei due punti;

• ∆λ `e il valore assoluto della differenza delle longitudini dei due punti

Nel caso in cui, viceversa, la proiezione del centro del cerchio non cada sul segmento, viene calcolato il minimo fra le distanze dei due estremi del segmento con il centro del cerchio.

(42)

5.4 La qualit`

a del segnale WiFi

Come abbiamo visto in precedenza, l’oracolo utilizza una qualit`a del se-gnale percentuale per determinare eventuali cambi di stato. Il valore scelto `e dunque una metrica qualitativa, che i singoli driver forniscono al kernel, e che dipende da vari fattori, quali la potenza di ricezione, il numero di pacchetti persi, il livello di rumore. La libreria iwlib fornisce per ciascuna rete indivi-duata da una scansione una struttura iw statistics, che contiene un’ulteriore struttura iw quality, all’interno della quale viene salvato tale valore.

Poiché il valore è un numero assoluto, vengono inizialmente richiesti tra-mite la libreria una serie di parametri utili alla scansione, fra i quali è conte-nuto il valore massimo che la qualità possa assumere. In tal modo è semplice calcolare il valore percentuale e utilizzarlo per i nostri scopi.

Si noti che, poiché la scansione delle reti è un’operazione che richiede di default i permessi di root, essa non viene scatenata ad ogni ciclo dell’oracolo (se questo viene eseguito con permessi di utente non privilegiato). Vengono invece restituiti i valori già presenti nella cache del sistema. Questo dettaglio può causare problemi al range, che potrebbe non essere aggiornato. Per ovviare a tale problema è sufficiente eseguire l’oracolo come superutente.

5.5 Aggiornamenti del database

Abbiamo già spiegato quali siano le table e i campi memorizzati dal da-tabase. Ci occupiamo ora di come vengano aggiornate le entry e del flag canaccess. Qualora si riscontri durante l’esecuzione una connessione a una rete presente nel database, essa viene marcata come accessibile e viene aggior-nato il flag canaccess del database per tutte le reti che possiedono il medesimo SSID. Nel caso di nuove inserzioni di reti con SSID già noto, si controlla se le altre reti memorizzate siano accessibili, settando appropriatamente il flag. Nel caso del range, invece, questo viene inizialmente settato a -1 nel da-tabase. Se successivamente durante una scansione si ottiene come risultato la rete e questa ha una qualità di ricezione percentuale maggiore di una certa

(43)

5.6 Costanti e scelte implementative 31

soglia, si compara la distanza con il range noto e si aggiorna il valore con il massimo fra i due.

Si è inoltre previsto, per quanto riguarda la tabella dei punti da cui si sono effettuate query, un valore temporale, in modo da potere, in future iterazioni del software, aggiornare i dati qualora essi siano obsoleti. Tale funzione non è però parte delle funzioni attualmente implementate nell’oracolo.

5.6 Costanti e scelte implementative

Vi sono una serie di constanti che influenzano in maniera fondamentale il comportamento dell’oracolo. L’impatto di tali costanti verrà ora discusso, considerando le ragioni della scelta di default implementata. Una prima co-stante fondamentale è la durata dello sleep() nel ciclo principale dell’oracolo. Tale costante, infatti, influenza il tempo medio fra i fix GPS ottenuti, un valore che viene poi utilizzato per selezionare le dimensioni dell’area attorno all’utente da selezionare. A causa del meccanismo di valutazione della dispo-nibilità della connessione, quanto più aumenta la lunghezza media del ciclo, tanto più cala la validità del dato sulla disponibilità. Per avere un valore affidabile ma non tenere continuamente sveglio il processore, si è optato per uno sleep di 1 secondo, che da origine a un’area da considerare di circa 2-3 m2 nel caso in cui la velocità di percorso sia quella di una persona che si muove a piedi.

Un’altra costante importante riguarda la scelta della percentuale minima di segnale (utilizzata anche nell’algoritmo 5.1), impostata di default al 30%. Questa percentuale viene utilizzata sia nel ciclo, per stabilire quando il se-gnale WiFi inizia a essere debole, sia nel calcolo del range per determinare quale sia il valore minimo per cui considerare un AP a portata. Quanto più tale valore aumenta, tanto più cala il range massimo per gli AP osservati. Ciò ha due effetti: da una parte aumenta la confidenza con cui affermiamo che nel range osservato è possibile la ricezione del segnale, d’altro canto ciò riduce sostanzialmente l’area stimata come coperta da segnale, rendendo

(44)

ra-32 5. Implementazione

ro il caso in cui si possa spegnere l’interfaccia WiFi a causa di una completa copertura dell’area circostante.

Viene utilizzata inoltre una costante per stimare i valori di range massimo ignoti, per gli AP che non sono ancora stati osservati. Tale valore viene settato dall’oracolo a 30m, un valore che viene considerato una stima della portata massima di un AP che utilizza il protocollo 802.11b/g in un contesto in cui siano presenti ostacoli solidi. Si era pensato in un primo momento di utilizzare un raggio diverso per gli AP 802.11n, che hanno una portata teorica doppia rispetto alle versioni precedenti del protocollo. Questo, tuttavia, non è risultato possibile utilizzando i dati derivanti da WiGLE. Si è effettuata pertanto una scelta che, seppur conservativa rispetto agli AP che utilizzino tecnologie più recenti, è una buona stima massima per quelli più datati.

Una menzione merita anche la superficie per la quale viene effettuato il caching di dati da WiGLE. Tale superficie non può essere troppo estesa, sia per non rallentare troppo il ciclo, sia perché WiGLE non permette di resti-tuire gli AP di un’area troppo grande. Si è pertanto scelta una superficie quadrata che inscrive un cerchio di raggio 1000m, in modo da avere, sempre considerando il caso di una persona che procede a piedi, una cache che co-pre circa 8 minuti di percorso (ammesso che si proceda semco-pre nella stessa direzione).

Un ultima costante rilevante `e la precisione desiderate (in percentuale) per quanto riguarda il calcolo della superficie occupata da segnale WiFi. Tale costante ha ripercussioni per quanto riguarda la durata del ciclo. `E stata settata, dopo qualche test sulle performance, al 3%.

(45)

Capitolo 6

Valutazione e sviluppi futuri

In questo capitolo avvieremo una discussione sull’efficacia dell’oracolo in un contesto reale.

6.1 Considerazioni preliminari

Nel caso di un software come l’oracolo, la complessità delle valutazioni finali è molto alta. Esistono infatti un’infinità di fattori che possono causare errori anche grossolani dell’oracolo e l’unico modo per poterli testare è una test sul campo, in cui si attraversano varie zone e si memorizzano vari para-metri dell’oracolo. Tali test risultano dunque non solo complessi, ma anche inevitabilmente parziali, in quanto non si possono effettuare in luoghi di-stanti e differenti fra loro. Perciò in questo capitolo utilizzeremo sia test con dati GPS simulati, senza reali spostamenti, sia test con un reale ricevitore e tenteremo di valutarne i risultati.

`

E ora necessario discutere in pratica come valutare l’efficacia dell’oracolo, a partire dagli obiettivi e dalle priorità indicati al capitolo 1. Come abbiamo specificato i parametri più significativi sono il consumo energetico e la di-sponibilità di connessione. Per stimare tali risultati nel contesto dei test sul campo, considereremo la percentuale di tempo in cui una NIC è attiva ma non utilizzata e la percentuale di tempo in cui a causa dell’oracolo

(46)

34 6. Valutazione e sviluppi futuri

mo la connettività. Come si vede, poiché non si è studiato un metodo per simulare le reti lungo un percorso, tali valori sono sensati solo nel caso dei test reali. Nel caso dei test simulati invece forniremo le caratteristiche del-l’area attraversata e confronteremo il comportamento dell’oracolo con quello più auspicabile.

6.2 Problematicit`

a

Prima di analizzare i risultati dei test, verranno considerate una serie di criticit`a note dell’oracolo. Alcune strategie per mitigare tali problemi verranno studiate poi fra gli sviluppi futuri.

6.2.1 La precisione della stima di disponibilit`

a

Seppur corredata di correzioni sullo stato attuale della rete, la stima di disponibilità di segnale WiFi è certamente poco efficace. Anche nel caso di aree molto piccole, la stima della disponibilità del segnale non è certo ideale. Perciò molto spesso l’oracolo ritiene sensato tenere attive entrambe le NIC, con un conseguente spreco di corrente. Inoltre, sebbene vi siano delle contromisure in atto per evitarlo, è certamente possibile perdere una connessione ad un AP WiFi prima di aver acceso l’interfaccia UMTS.

Inoltre, poiché vi è un’incertezza del fix del GPS, tale problema diviene ancora più evidente nel caso si abbiano errori nella posizione molto elevati, che portano ad un aumento dell’area da considerare ed a una conseguente diminuzione della superficie circostante coperta da segnale.

Un ulteriore problema riguarda l’altitudine. Se il ricevitore GPS è perfet-tamente in grado di fornire una posizione tridimensionale, in cui sia presen-te anche l’altitudine del dispositivo (sebbene l’altitudine abbia errori molto ampi), il database di WiGLE non contiene tale valore. Questo potrebbe con-durre, ad esempio, ad uno scenario in cui viene accesa un’interfaccia di rete anche se l’AP associato è parecchi metri sopra il device e pertanto non è a portata. Fortunatamente questo problema è mitigato dal fatto che il

(47)

databa-6.2 Problematicit`a 35

se di WiGLE viene per lo pi`u aggiornato da utenti che camminano al livello del suolo con un dispositivo mobile, che quindi non rilevano AP posizionati ad altitudini diverse.

Vi è poi un problema intrinseco nell’approccio utilizzato per stimare l’area percorsa in un dato tempo. Se l’indicazione della velocità è una stima valida, a meno di improvvise accelerazioni o decelerazioni, vi è un valore la cui stima precisa è impossibile. Si tratta della durata del prossimo ciclo, che come per ogni programma è inconoscibile. La durata oltretutto è fortemente influenzata dal numero di AP trovati, dal numero di richieste a WiGLE necessarie, dal tempo per avere un fix GPS. Tale problematica purtroppo non può essere evitata ed ogni tentativo di stima, anche diverso da quello implementato nell’oracolo, non può essere preciso e pertanto influenza le valutazioni sulla disponibilità.

Un ulteriore difetto dell’approccio utilizzato riguarda la possibilità, per quanto riguarda gli AP di una stessa WLAN, di supportare il cosiddetto roaming involontario. Tramite tale meccanismo, analogo a quello usato dalle reti cellulari, consente alla NIC di effettuare un passaggio orizzontale, senza richiedere una nuova associazione, all’AP che offra miglior qualità del segna-le. L’oracolo, nel caso in cui ci si trovi in una zona con molti AP eterogenei accessibili, accende l’interfaccia WiFi senza curarsi dei passaggi da una re-te all’altra. Nel caso in cui si utilizzi ABPS ciò condurrebbe a perdite di connessione non desiderate.

6.2.2 L’oracolo e i consumi

Un’altra criticit`a dell’oracolo riguarda i consumi di energia legati alle operazioni da esso eseguite, tra cui l’utilizzo costante del GPS e le scansioni WiFi. Nel caso si utilizzi l’oracolo in concomitanza al sistema ABPS si avrebbero indubbiamente dei vantaggi in termini di consumi energetici, in quanto si evitano in parte i consumi derivanti dall’utilizzo contemporaneo di due NIC in trasmissione. Se, invece, ABPS non viene utilizzato, `e lecito chiedersi se sia conveniente utilizzare l’oracolo, visti i consumi aggiuntivi che

(48)

esso provoca. Il consumo di un ricevitore GPS `e abbastanza elevato [13] e ha effetti nefasti sull’utilizzo di un dispositivo mobile. Tuttavia non vi sono strategie in grado di minimizzare tale impatto, se non quella di aumentare il timeout fra i cicli dell’oracolo. Cos`ı facendo, per`o, si riduce di molto l’efficacia del software.

Figura 6.1: Il consumo di una scansione WiFi in un dispositivo mobile con schermo attivo [14]

Un altro aspetto da considerare è il consumo di una NIC WiFi durante la scansione di rete. Tale processo è energeticamente dispendioso (vedi 6.1) e viene effettuato ad ogni ciclo ogni qual volta il WiFi è attivo se l’oraco-lo viene eseguito con privilegi di superutente. Questo effetto può tuttavia essere mitigato eseguendo il software senza privilegi particolari. In questo modo verranno usati i risultati in cache rilevati dalle scansioni passate. Tali risultati, però, potrebbero non essere accurati. Se nel caso dell’AP a cui si è associati non si rilevano problemi per quanto riguarda la rilevazione della qualità del segnale, essa può risultare errata per gli altri AP nelle vicinanze. Il sistema, infatti, mantiene in cache i risultati finché l’ultimo beacon frame ricevuto non sia distante 30 secondi, un tempo piuttosto ampio. Tali scan-sioni vengono tuttavia effettuate periodicamente dal kernel anche nel caso si sia associati a una rete, si potrebbero pertanto studiare strategie per non svegliare l’interfaccia e utilizzare i dati delle scansioni automatiche.

(49)

6.2 Problematicit`a 37

6.2.3 WiGLE e i dati sugli AP Wifi

Per quanto sia innegabile l’importanza di WiGLE nell’implementazione dell’oracolo, esso ha purtroppo delle limitazioni che creano dei problemi per l’utilizzo pratico dell’oracolo. Prima di tutto occorre evidenziare come l’uti-lità dell’oracolo sia vincolata in parte alla possibilità di accedere ad internet per richiedere dati a WiGLE. Con i moderni dispositivi mobili la maggior par-te dei contratti impone forti limitazioni alla quantità di dati che è possibile scaricare. Per quanto le query a WiGLE non abbiano dimensioni elevatissi-me, esse possono raggiungere facilmente il MB. Se si effettuano di frequente, dunque, esse possono portare a un esaurimento del traffico in breve tempo.

Abbiamo in precedenza affermato come esista un limite al numero di richieste effettuabili in un dato tempo a WiGLE. Questo, seppure vengano adottate delle strategie per mitigare questa situazione, causa inevitabilmente una diminuzione dell’efficacia dell’oracolo, che non è più in grado di deter-minare la situazione circostante qualora la velocità di spostamento lungo il percorso sia troppo elevata.

Un altro problema riguarda la presenza di AP pubblicamente accessibili (o perché senza chiave di cifratura o perché con chiave nota) che richiedono però un’autenticazione tramite una pagina di benvenuto HTTP. Tali reti, che verrebbero considerate dall’oracolo come accessibili, di fatto interrompereb-bero la possibilità di connessione, reindirizzando ogni richiesta alla pagina di login iniziale.

Un’ulteriore criticità riguarda la modalità con cui vengono individuate le reti note. Esse vengono marcate come accessibili qualora vi si connetta, aggiornando di conseguenza il database a partire dal loro SSID. Questa è la strategia adottata dalla maggior parte di gestori di reti WiFi (es Net-workManager), che determinano se una rete sia accessibile dall’SSID ad essa associato. Ciò però conduce inevitabilmente ad errori, sia a causa di SSID generici impostati dai vendor degli AP (LINKSYS, Sitecom, etc), sia per eventuali nomi che risultano casualmente uguali. Purtroppo a tale problema non esiste una soluzione completa, tanto che esso affligge ciascun software

(50)

che gestisca la connessione a reti WiFi.

Occorre infine considerare il caso di un’area non precedentemente visi-tata e che non contiene AP marcati come ”free“ da WiGLE, ma di cui si possiedono le credenziali d’accesso. Tale situazione, poiché l’oracolo, allo stato attuale, non è in grado di discriminare lo stato delle interfacce di rete, porta l’oracolo a passare allo stato UMTS ON. In tale modo, esso non uti-lizza i risultati delle scansioni WiFi e non apprende la situazione delle reti circostanti. Affronteremo più tardi come si sia mitigato tale problema du-rante i test, sia quelli con posizione virtuale, sia quelli con posizione reale ed eventuali altre soluzioni. Sarebbe sensato pensare che basti far riconoscere all’oracolo lo stato dell’interfaccia di rete WiFi per cambiare lo stato in modo coerente. Tuttavia, poiché non sono stati implementati metodi per spegnere le interfacce realmente, ciò condurrebbe a una grande difficoltà nell’effettuare test, che si svolgono con l’interfaccia WiFi sempre accesa per poter avere un riscontro della connessione ad un qualche AP.

6.3 I test

Riportiamo ora i risultati dei test effettuati, in parte utilizzando posizioni gps fittizie, in parte con un GPS vero e proprio.

6.3.1 Test con gpsfake

Per effettuare test significativi con gpsfake si sono dovute effettuare sem-plici modifiche al codice per permettere i test in modo coerente. Poiché i test vengono effettuati da una stessa zona, si sono rimossi dallo switch fra stati tutti i riferimenti alla presenza di una connessione e al caso in cui si sia connessi da un certo numero di cicli allo stesso AP, che avrebbero in-fluenzato i risultati. Come area per il testing si è scelta via Zamboni, per tutto il suo percorso, da Piazza di Porta Ravegnana a porta San Donato. Si sono inoltre impostati nel database come accessibili gli AP di Iperbole ed ALMAWIFI. Poiché i range di tali AP sono ignoti, essi vengono stimati a

(51)

6.3 I test 39

Figura 6.2: Una visualizzazione del risultato del test utilizzando gpsfake su via Zamboni. I marcatori segnalano i mutamenti di stato

30m dall’oracolo. Come si vede da 6.2 il comportamento dell’oracolo è quello atteso. La NIC WiFi viene spento fino a via S.Giacomo, di fronte alla sede della Scuola di Giurisprudenza, dove secondo WiGLE è presente un AP. A questo punto sorge un piccolo problema nel test e si riscontra una velocità molto più alta del dovuto a causa delle limitazioni di gpsfake, che non è in grado di interpretare i timestamp delle sentence NMEA. A causa di ciò il WiFi rimane acceso fino a piazza Verdi. Qui viene disattivata l’interfaccia UMTS finché è disponibile ALMAWIFI, poco prima di piazza Puntoni. Vie-ne spento successivamente il WiFi fino alla porta, quando si passa di fronte al Dipartimento di Matematica.

Sebbene WiGLE non sembri contenere i dati relativi alle reti Iperbole Wireless presenti, il risultato di questo test `e incoraggiante: il comportamento dell’oracolo, a parte un piccolo problema della suite di test prima di piazza Verdi, appare perfettamente in linea con l’output atteso, con uno spreco di energia minimo e la massima disponibilit`a di rete possibile.

(52)

6.3.2 Test con ricevitore GPS

Il test condotto con un GPS reale è stato effettuato utilizzando un sen-sore contenuto in uno smartphone Android e trasmesso tramite bluetooth al PC. Tale test è stato effettuato sempre su via zamboni da via Giuseppe Petroni fino a poco dopo piazza Puntoni. A causa dell’incertezza dei dati trasmessi via bluetooth, misurata da gpsd in circa 100m sia per la latitudine che per la longitudine, la totalità del tragitto è avvenuta con entrambe le interfacce di rete attive. Seppure non si siano verificati mutamenti di stato, per la totalità del percorso le scansioni WiFi hanno evidenziato la presen-za di reti ALMAWIFI, alcune delle quali non sono presenti sul database di WiGLE. Inoltre sono stati aggiornate correttamente le portate massime di alcuni AP. Seppure incompleto, tale test mostra la validità dell’approccio an-che in un caso d’uso reale, nel quale l’incertezza nel fix GPS porta l’oracolo a compiere scelte meno drastiche rispetto ai test teorici. Se si è certamente sprecata energia, si consideri tuttavia il fatto che non si era predisposta una connessione automatica alle reti, che avrebbe portato, in caso di lunghi pe-riodi di connessione, allo spegnimento della NIC UMTS. La disponibilità di connessioni WiFi è stata invece massimizzata.

6.4 Sviluppi futuri

Si affrontano ora le prospettive di sviluppo per l’oracolo con particolare attenzione ai problemi segnalati nel capitolo precedente.

6.4.1 Un’altra fonte di dati per effettuare scelte

Al fine di migliorare l’efficacia dell’oracolo sarebbe interessante l’imple-mentazione di un ulteriore fonte di dati, in particolare quella descritta nel capitolo riguardante la progettazione. Si potrebbe, stimando la direzione futura sulla base di quelle precedenti, effettuare una valutazione pi`u precisa della disponibilit`a di connessioni WiFi lungo il percorso, mantenendo