Distributed Algorithmic Mechanical Design: Applications to Wireless Ad Hoc Networks

Distributed Algorithmic Mechanical Design:

Applications to Wireless Ad Hoc Networks

Antonio Caruso

Università degli studi di Lecce

Wireless Multi-Hop Ad Hoc Networks

• Considerate un insieme di computer mobili, autonomi, alimentati da batterie, es. palmari, portatili, smart phones.

• Se i nodi sono dotati di interfaccia wireless (una

radio), essi possono formare una rete wireless ad hoc.

• Non esistono unità specializzate (Access Point) per svolgere il compito di inoltro dei pachetti (routing). I nodi cooperano tra loro per inoltrare i pachetti

(svolgono anche il ruolo di router).

Vantaggi delle reti Ad Hoc.

• Sistema completamente distribuito: nessun punto di centralizzazione.

• Creazione, configurazione e utilizzo della rete immediati.

• Rete peer-to-peer: robustezza, tolleranza a eventuali guasti.

Problematiche

• Controllo distribuito

• I nodi devono cooperare con i vicini

• Ma il loro movimento rende complicata la

cooperazione (la rete è fortemente dinamica)

• I nodi possono essere di diverso tipo da microsensori a veri e propri PC portatili.

Applicazioni delle reti Wireless Ad Hoc

• Comunicazioni in ambienti ostili: scenari militari.

• Gestione delle emergenze: applicazioni di sicurezza in ambito civile.

• Installazioni commerciali: ampliamento della copertura delle reti wireless tradizionali, e miglior uso della

banda.

• Reti di Sensori, per il monitoraggio dell’ambiente esterno.

Multi-Hop Wireless Ad-Hoc Networks

Obstacle

• La potenza della radio è limitata:

Ogni nodo può

comunicare solo con i suoi vicini entro una certa distanza.

• La comunicazione con altri nodi richiede cooperazione da parte di vicini (servizio di inoltro - routing).

• I protocolli di inoltro dei pachetti sviluppati per reti fisse

Protocolli per il Routing

• Sono stati sviluppati molti protocolli per risolvere il problema del routing dei pacchetti.

• In questo talk vogliamo evidenziare che:

Una rete ad-hoc può essere vista come una rete di Agenti Autonomi.

• Normalmente gli Informatici assumono che gli agenti siano obbedienti: essi eseguono correttamente e

spontaneamente i protocolli sviluppati.

• In alcuni casi è prevista l’esistenza di avversari che

giocano contro il sistema. Per esempio nell’analisi della sicurezza dei protocolli.

Agenti Strategici, Teoria dei Giochi.

• Gli economisti modellano i sistemi multi-agenti attraverso l’idea del comportamento strategico.

• Teoria dei Gioci: i giocatori sono razionali e egoisti, scelgono in modo da massimizzire la loro utilità.

• Non è quindi detto che eseguano correttamente un certo algoritmo, ma possono essere incentivati a farlo.

• L’uso della teoria dei giochi non è una novità: l’aspetto importante è lo sviluppo di meccanismi di

incentivazione, o mechanism design.

Cooperative Routing in Ad Hoc Networks

• In alcuni scenari, i nodi della rete sono gestiti da un unica autorità, o i gestori sono disposti a cooperare.

• In molti altri, la cooperazione nell’eseguire un certo protocollo non è scontata.

• Il comportamento egoistico (selfish) è nel caso delle reti ad-hoc distruttivo. l’Egoismo infatti impatta proprio il servizio più importante per l’esistenza della rete: la disponibilità dei nodi di inoltrare pacchetti per conto terzi.

Cooperazione e Inoltro dei pacchetti

u

w

v

z

Meccanismi per la Cooperazione

• Il modo più semplice per stimolare la cooperazione nell’ipotesi di agenti razionali è usare incentivi.

• Si possono usare due forme diverse:

Sistemi di Reputazione o

Trasferimenti di Denaro

La propria reputazione è importante

• In questi sistemi ogni nodo controlla il comportamento dei suoi partner.

• Se scopre che un altro nodo non segue il protocollo

viene etichettato come “cattivo” e questa sua opinione viene propagata nella rete.

• Questo porterà all’esclusione del nodo da parte del resto della rete.

• Ma allora l’interesse di ogni nodo a deviare dal

protocollo sarà tanto inferiore quanto più è elevato il rischio di essere escluso dalla rete.

Trasferimento di risorse (Denaro)

• Un nodo che vuole spedire un pacchetto deve pagare una certa quantità di denaro (virtual money) per

ricevere il servizio di inoltro dai suoi vicini.

• Il mittente è disposto a pagare in funzione della sua necessità a spedire pacchetti verso altri nodi.

• I nodi intermedi sono invogliati a fornire il servizio di inoltro perchè il denaro ricevuto potrà essere usato da loro per inoltrare i loro pacchetti.

Scenario di utilizzo

Modellazione del Gioco (1)

• Esistono tre ruoli per i nodi: il mittente (S), il destinatario (D) e gli intermediari.

• Il mittente S ha come informazione privata il suo desiderio di spedire o meno pacchetti. In termini monetari, pagherà un prezzo m per pacchetto.

• Per comunicare con il destinatario D, dovrà pagare un prezzo di mercato p_S(D). La funzione d’utilità del

mittente è pertanto:

u(S) = m - p_S(D)

• Se non può essere stabilita alcuna connessione l’utilità è zero.

Modellazione del Gioco (2)

• Consideriamo un nodo intermedio arbitrario v.

L’informazione privata del nodo, è la sua disponibilità a inoltrare pacchetti per altri nodi.

• Può essere modellata come un costo C_v che terra conto di molti fattori: il livello della batteria, l’uso da parte di v della rete per se stesso, etc.

• La funzione di utilità di un nodo intemedio sarà:

u(V) = Pay(v) - C_v

• Dove Pay(v) è il denaro ricevuto da v per il servizio. Se v

Modellazione del Gioco (3)

• Il destinatario D, non è parte del gioco, in quanto si assume che l’access point sia gestito da un service provider che ha interesse a fornire un servizio equo.

• Egli svolge il ruolo di arbitro del sistema, calcola il percorso da S a D ottimale, il pagamento che S deve effettuare e i premi per i nodi intermedi.

• Lo scopo dei nodi è massimizzare le loro funzioni di utilità, il

comportamento è modellato attraverso un insieme di strategie che i nodi possono adottare.

• Una delle strategie possibili è proprio seguire il protocollo,

dichiarare correttamente i loro prezzi/costi e spedire/inoltrare i pacchetti dati e di controllo, tale strategia è detta: True Telling

Il routing è la nostra funzione sociale

• L’obiettivo di chi sviluppa il protocollo è sviluppare un meccanismo di incentivi che massimizzi sia una certa funzione sociale SIA

l’utilità dei nodi.

• Nel caso studiato, vogliamo che i nodi partecipino effettivamente alla rete, ma che paghino il minimo possibile per avere/fornire servizi tra essi.

• Informalmente vogliamo che sia qualcosa del tipo: “stabilisci la comunicazione tra S e D usando il percorso più efficiente”.

• Il problema del Mechanism Design è una specie di problema di

reverse engineering: trovare i giusti incentivi (pagamenti) in modo che la funzione sociale venga massimizzata attraverso il

comportamento egoistico dei nodi.

Strategy Proof Mechanism

• Un modo per arrivare all’obiettivo è focalizzare l’attenzione sulle strategie dominanti.

• Una strategia è dominante se massimizza la funzione di utilità di un giocatore indipendentemente dalle strategie usate dagli altri.

• Cercheremo delle regole del gioco in modo che il True Telling sia una strategia dominante del gioco.

• Un meccanismo che soddisfa la condizione sopra si dice truthful o incentive compatible o strategy proof.

• E’ una condizione forte sul gioco, i giocatori non hanno interesse a deviare dalla strategia true-telling.

Razionalità Individuale

• Un altra condizione che deve essere soddisfatta dal meccanismo del gioco è la razionalità individuale (individual rationality).

• Un nodo ha convenienza a partecipare al gioco.

• Questa condizione è soddisfatta se la sua funzione di utilità è maggiore di zero.

Non Consideriamo

• Collusione tra nodi per massimizzare in modo congiunto le proprie utilità.

AdHoc-VCG

• Protocollo di routing con le seguenti caratteristiche:

– trova i percorsi tra S e D

– spedisce i pachetti lungo il percorso di costo minimo

– provato formalmente essere strategy proof e individualmente razionale (ma tranne per S.).

– basato su VCG (meccanismo Vickrey-Clarke-Groves)

• Basato sulla seguente idea:

1) quando S vuole spedire un pacchetto (connettersi con l’AP nel nostro scenario) inizia una fase di ricerca di percorsi fornendo l’identità del destinatario (AP nello scenario).

2) Alla fine di 1, S riceve un percorso P e un costo associato. Il

prezzo p>=costo(P) pagato da S viene diviso tra i nodi che sono sul percoso P con regole predefinite.

AdHoc-VCG

• Problemi: usa costi per ogni arco, e O(n³) messaggi.

• Il mittente viene considerato non necessariamente razionale ma comunque partecipante al gioco, ipotesi forte e quasi sempre false (falsa proprio nel nostro scenario).

• Si suppone che finita la fase di ricerca il mittente sia sempre disponibile a pagare per ogni pacchetto il

corretto importo.

• Ma nello scenario mostrato, significa che il mittente se vuole spedire è costretto a accettare un costo per lui

COMMIT (Eidenberg, 2005)

• Questo protocollo oltre al routing risolve anche un altro problema (Topology Control o Controllo della Topologia) cioè decide il livello di potenza usato da ogni nodo

nell’uso della radio (serve per ottimizzare i consumi ma anche l’uso dello spettro).

• Usa i pesi sui nodi e riduce il numero di messaggi a O(n²) ( = grado massimo = O(1)).

• Sopratutto risolve il secondo problema: non fa assunzioni sul mittente. E’ truthful e individually rational per il mittente.

COMMIT Protocol

• Se S vuole spedire un pacchetto: fare una “richiesta di

connessione” specificando il massimo prezzo MAXP che si è disposti a pagare.

• Se esiste un percorso di costo minore del prezzo specificato da S, S è obbligato a accettare quel

percorso: se un altro percorso di costo minore potrebbe essere formato lui non può rifiutare comunque un offerta al prezzo MAXP.

• Se il prezzo è superiore S può rifiutare. In questo modo chi spedisce ha una garanzia di non spendere più di quanto

preventivato.

Prezzi in VCG

• Sia c(P) è il costo di un percorso tra (S,D)

• MP il Percoso di costo Minimo.

Percorso di Rimpiazzo per un nodo v

Per ogni v != S, D in MP, P^-v è un percorso ottimo tra (S,D) che non include v, e c(P^-v) è il suo costo.

Il prezzo che v deve pagare è definito come:

Prezzo(v) = c(P^-v) – c(MP) + cv

dove c_v è il costo di inoltro dichiarato da v. Se un nodo non è sul percorso minimo, il prezzo è 0.

Esempio

•MP = { S, u, v, z, D }. costo = 15+19+12 = 46.

pagamenti con VCG:

•Prezzo(u) = c(P^-u) – 46 + cu = 53-46+15 = 22

•Prezzo(v) = c(P^-v) – 46 + c_v = 48-46+19 = 21

•Prezzo(z) = c(P^-z) – 46 + cz = 48-46+12 = 14. Quindi 22+21+14=57>46

D

15 18

20

Il costo della cooperazione

• Abbiamo visto che con un meccanismo VCG, il costo

pagato per il servizio (57) è superiore al costo reale (46).

• Nella teoria dei giochi è dimostrato (sotto assunzioni

ragionevoli) che questo è intrinseco ad ogni schema VCG, che sia strategy proof e con razionalità individuale.

• E’ dovuto alla necessità di invogliare i nodi che

forniscono il servizio di inoltro, pagando un surplus rispetto al costo dichiarato.

• Il surplus (57-46) è detto “costo della cooperazione”.

Prezzi in COMMIT

• In COMMIT anche il mittente prende parte al gioco. Il prezzo pagato dal mittente Cs(D) potrebbe essere definito come in VCG = Somma dei prezzi dei nodi sul percorso da S a D. E’ interpretabile come regola di decisione nell’attivare il percorso (Se Cs(D)>m, viene rifiutato).

• Non va bene!. I nodi nel percorso minimo possono strategicamente incrementare il loro guadagno riportando costi più alti.

• Esempio con m=56: non ci dovrebbe essere comunicazione poichè il costo è 57. Se z dichiara 13 invece di 12-> (MP = 47) e il costo del percorso scende a 55 < 56 e viene attivato. z incrementa la sua utilità da 0 a 2 dichiarando il falso.

COMMIT

Costo corretto per il mittente:

Dato il percorso di costo minimo MP tra S e D, P^-MP è un

percorso di costo minimo tra S e D che esclude tutti i nodi di MP tranne (S,D).

c_s(D) = c(P^-MP)

Evita il comportamento strategico da parte di qualche nodo sul percorso. I nodi che forniscono il servizio di

inoltro non possono portare il costo del percorso sotto m.

Aumenta il costo di cooperazione. Potrebbe essere pagato in parte dall’AP per invogliare i mittenti.

Ricapitolazione

COMMIT è formalmente:

• Cost Efficiency: Se i nodi scelgono true-telling, COMMIT trova i percorsi di costo minimo.

• Basso numero di messaggi. O(n²)

Per il mittente e per i nodi che inoltrano i pacchetti:

• Truthfulness: true-telling è una strategia dominante

• Individual rationality: l’utility è sempre >=0, i nodi