Non accavallatevi! Ovvero: la teoria dei giochi applicata alle telecomunicazioni

ResearchBlogging.org Non sempre la somma degli interessi individuali produce un vantaggio per la comunità, specialmente in presenza di risorse scarse.

E’ quello che ha potuto verificare lo stato maggiore della Apple lo scorso giugno durante la presentazione del nuovo iPhone4 alla Apple developer conference. Steve Jobs voleva appunto mostrare le meravigliose capacità del proprio gioiellino, e come prima cosa cercò di collegarlo alla rete Wi-Fi presente in sala. Ma la sala era piena di centinaia di appassionati, tutti con il loro laptop connesso alla rete, tutti pronti a bloggare/twittare e facebokare le primissime impressioni dalla sala. E come chiunque partecipante ad una qualsiasi conferenza ha potuto sperimentare, semplicemente il Wi-Fi non andava: troppo traffico, troppe stazione che cercano di connettersi contemporaneamente.


Al che Jobs sfodera il suo sorriso e annuncia: “Ci sono 570 apparecchiature Wi-Fi in questa stanza, e semplicemente non c’è abbastanza banda per tutti. Per continuare la dimostrazione, vi invito tutti a spegnere i vostri laptop e a depositarli ai vostri piedi”. Alcuni dei presenti obbedirono, ma molti invece continuarono a tenere acceso il proprio. La demo non fu un quello che si dice un completo successo.

Forse c’è una lezione dietro tutto ciò, e per spiegarla dobbiamo ricorrere a una branca della matematica chiamata “teoria dei giochi“. La situazione è infatti simile al famoso “dilemma del prigioniero“. Tutti i giornalisti in sala avevano un interesse preciso: essere i primi a poter postare notizie e impressioni sul nuovo modello, in tempo reale dalla sala. Ma se tutti tenevano il Wi-Fi acceso, nessuno poteva comunicare. Se una buona parte avesse spento il PC, gli altri avrebbero postato per primi, e quindi ne avrebbero ottenuto un vantaggio. Quindi, se tutti ricercano il loro migliore interesse, nessuno raggiunge l’obiettivo.

Gli autori dell’articolo di cui ci occupiamo oggi sostengono che è possibile applicare risultati della teoria dei giochi per evitare situazioni del genere in presenza di banda limitata. Come sapete, la banda del Wi-Fi è limitata, e va condivisa tra tutti i partecipanti presenti nella stessa area e connessi allo stesso “gateway”.

Quest’ultimo, detto anche “coordinatore”, si occupa di distribuire la banda tra i vari partecipanti utilizzando un meccanismo a divisione di tempo:  il coordinatore assegna in maniera esclusiva la banda disponibile per un “time slice” di alcuni millisecondi a ciascuno dei trasmettitori a turno. Ad esempio, supponendo un time-slice di 2 millisecondi, e se ci sono 4 dispositivi che desiderano trasmettere, ognuno di loro potrà trasmettere per 2 millisecondi ogni 8, prendendosi quindi effettivamente 1/4 della banda disponibile.

In realtà, questo meccanismo non sempre funziona benissimo per vari motivi. Infatti, non tutti i dispositivi sono in grado di comunicare con la stessa qualità. Se uno dei 4 è più lontano, oppure dietro una parete, sperimenterà una qualità del segnale minore, e quindi comunicherà più lentamente. Se invece uno sta proprio sotto il coordinatore, magari comunica molto meglio. Misuriamo la “qualità” del canale di comunicazione come picco massimo di byte che possono essere trasmessi al secondo. Per esempio, supponiamo che al massimo della qualità si possa comunicare a 10 Mbytes al secondo, e al minimo si possa andare a 1Mbytes al secondo. Purtroppo, per rendere le cose più difficili, la qualità della comunicazione varia grandemente con il tempo: i trasmettitori si possono muovere, all’aperto le condizioni metereologiche possono influire, ecc.

Se la rete in questione (come nel caso del Wi-Fi) ha un coordinatore, per ottimizzare la comunicazione di solito si cerca di far comunicare di più chi ha la banda migliore. Quindi, invece di utilizzare time-slices tutte di dimensioni uguali, si varia la dimensione dando una time-slice proporzionale alla qualità del segnale: migliore qualità, maggiore la time slice. Questo è abbastanza facile da fare, perché il coordinatore, quello che decide, monitora la qualità dei partecipanti e quindi sa chi ha il canale migliore, e decide in maniera ottimale.

Supponiamo ora una rete senza coordinatore. Queste reti sono “peer-to-peer”, o anche dette reti “Mobile Ad-Hoc”. Non essendoci un coordinatore, tutti i partecipanti devono mettersi d’accordo fra di loro per decidere le time-slices usando un regola. Si potrebbe fare così: ognuno annuncia la propria qualità di trasmissione percepita; a questo punto, tutti applicano la formula per decidere la dimensione e l’ordine delle time-slices; poi si comincia a comunicare. Dopo un po’, ci si rimette d’accordo sulla qualità del canale, ecc.

Questo tipo di approccio però è soggetto a un problema: un trasmettitore potrebbe mentire! Potrebbe dichiarare una qualità molto alta, in modo da beccarsi un time-slice il più grande possibile. Se tutti facessero così, l’utilizzo finale della rete sarebbe scarso, sub-ottimale.

Gli autori quindi propongono un meccanismo di punizioni per chi si comporta male. Si monitora la quantità di dati trasmessi effettivamente da una stazione e si confronta con quello dichiarato. Chi ha fatto il furbo viene “bannato” (ovvero non ha diritto a trasmettere) per un po’ di tempo. Questo il succo a grandi linee. L’approccio è naturalmente un po’ più complicato perché bisogna stare attenti ad alcuni dettagli che qui salterò, e che se volete potete andarvi a leggere sull’articolo originale.

La teoria dei giochi è stata quindi applicata a un nuovo campo di applicazione, e mi sa continuerà ad essere utilizzata parecchio nel futuro delle telecomunicazioni!

RIFERIMENTI

Ji, Z., & Liu, K. (2007). COGNITIVE RADIOS FOR DYNAMIC SPECTRUM ACCESS – Dynamic Spectrum Sharing: A Game Theoretical Overview IEEE Communications Magazine, 45 (5), 88-94 DOI: 10.1109/MCOM.2007.358854

La storiella di Jobs è presa da questo articolo divulgativo di uno degli autori.

Posta un commento o usa questo indirizzo per il trackback.

Commenti

  • picchiopc  Il 18 maggio 2011 alle 02:30

    Davvero un post interessantissimo 😀

  • dioniso  Il 18 maggio 2011 alle 12:24

    Interessante. Ho imparato qualcosa di nuovo.
    Saluti

  • evilripper  Il 18 maggio 2011 alle 15:48

    si sarebbe un approccio molto più democratico! però è stressante il fatto che ci possa essere sempre qualcuno che cerca di “frodare”! se fossero tutti onesti! 😀 😀
    ps
    perchè gli organizzatori non hanno pensato(forse proprio perchè non ci avevano pensato) di mettere una rete wifi dedicata (magari nascosta) con password solo per steve?? 😀

    • glipari  Il 18 maggio 2011 alle 19:57

      Ciao, la teoria dei giochi cerca di risolvere il problema dell’onestà alla radice. La punizione è un deterrente perché tutti siano stimolati a comportarsi bene, ma anche un premio nella direzione giusta potrebbe funzionare altrettanto bene. Gli autori dell’articolo hanno analizzato varie possibilità premi/punizioni, e le hanno valutate matematicamente tramite la teoria dei giochi.

      Riguardo alla seconda domanda: non so esattamente cosa sia successo, bisognerebbe avere qualche informazione in più. Azzardo: gli organizzatori della conferenza, non ci hanno pensato credo perché avevano già esaurito la banda Wi-Fi a disposizione. Quando ci sono diversi gateway/router in un’area, ognuno si prende una banda di frequenze (chiamato anche “canale”) diversa da quegli altri, in modo da non darsi fastidio a vicenda. Infatti, se due router andassero sullo stesso canale si farebbero intereferenza tra di loro.
      Ora, il numero di canali disponibili è limitato, quindi al massimo ci possono essere un certo numero di router attivi in una certa zona. Con 570 utenti da supportare, secondo me avevano esaurito i canali.
      Non sono un esperto del protocollo IEEE 802.11 (volgarmente chiamato wi-fi) ma è possibile che quando c’è un grande numero di dispositivi si abbiano grossi problemi di interferenza anche sui canali protetti da password (teoricamente liberi). In gergo si dice che il protocollo “non scala” con il numero di dispositivi. Cmq, domani chiedo agli esperti del mio dipartimento e semmai ritorno sulla mia risposta.

  • Vincenzo  Il 19 maggio 2011 alle 20:03

    Da leggere assolutamente soprattutto la prima parte applicando lo stesso ragionamento alla politica.

  • Fioravante Patrone  Il 20 giugno 2011 alle 09:09

    Mi accodo a chi ha già detto che si tratta di un tema interessante. Senza dubbio la teoria dei giochi sta assumendo un ruolo importante per le telecomunicazioni.
    Un episodio personale, che mostra quanto interesse ci sia per questi temi: nel 2010 ho tenuto (assieme ad un collega, Moretti) un corso di dottorato presso Telecom ParisTech, dedicato alla teoria dei giochi. Il successo è stato tale che abbiamo dovuto clonarlo…
    Aggiungo, come considerazione personale, che quest’ambito di applicazione e, più in generale, le applicazioni “ingegneristiche” (che sono in espansione) immagino avranno un benefico effetto sulla teoria stessa.

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: