1/20 S-Lanes - Ein schlankes Overlay zur motivierten Dienstvermittlung in mobilen Ad-hoc-Netzen Universität Karlsruhe Diplomarbeit von Georgios Papadopoulos

1/20

S-Lanes - Ein schlankes Overlay zur motivierten Dienstvermittlung in mobilen Ad-hoc-Netzen

Universität Karlsruhe

Diplomarbeit von Georgios Papadopoulos

Betreuer: Dipl.-Inform. Philipp ObreiterDipl.-Inform. Michael Klein

2/20

Überblick

• Zielsetzung der Arbeit• Einführung

– Lane Struktur– Funktionsweise– Evaluierung von Lanes

• Analyse des Fehlverhaltens– Problem– Klassifizierung

• Konzeption eines Anreizschemas– Anreizmuster– Erweiterung der Protokolle

• Evaluation• Zusammenfassung & Ausblick

3/20

Zielsetzung der Arbeit

• Implementierung der Lanes-Protokolle und Evaluierung der Lane-Struktur

• Analyse des Kooperationsverhaltens autonomer Geräte

• Anreizschema entwerfen, das Lanes-Protokolle robust gegen nicht kooperative Geräte macht

4/20

Lanes Struktur

1

2

3

4

5

6

7

8

9

10

Lane 1

Lane 2

Eigenschaften• Logische Verbindungen• Intra-Kommunikation: direkt• Inter-Kommunikation: anycast

X

Vorgänger

Nachfolger

Idee

Zusammenschluss von Geräten unter gleichen anycast Adressen

linke anycast Adresse

rechte anycast Adresse

Effektive und effiziente Dienstsuche

5/20

Funktionsweise

6

7

8

9

10

11

12

13

14

15

Lane 2

Lane 3

1

2

3

4

5

Lane 1

Dienst ankündigen

Dienst suchen Dienst

gefunden

Gerät 3 bietet den Dienst

6/20

Algorithmen der Lanes-Struktur

Für die Realisierung der Lanes-Struktur werden folgende Algorithmen eingesetzt:

• Login/Logoff-Algorithmus – Zutritt in die bzw. Austritt aus der Lane

• Dienstankündigung-Algorithmus– Dienstbekanntgabe innerhalb der Lane

• Dienstsuche-Algorithmus– Interne und anycast Suche

• Split-Algorithmus, Merge-Algorithmus– Korrektur der Lanegröße

• LaneBroken-Algorithmus– Korrektur nach unangekündigtem Austritt

• Algorithmen für Netzpartionierung/Reintegration

Ping-Nachrichten: Sorgen für die Pflege der Lanes

7/20

0

5

10

15

20

25

30

35

0 10 20 30 40 50

Triviale Suche

Lanes

Evaluierung von Lanes

Dynamik [ Verweildauer in Min.]

Aufwand [ #Nachrichten/Suchanfrage]

Einstellungen: 1. 15 Geräte 2. Testdauer 3600s 3. Aktion jede 60 Sekunden 4. Ping Nachrichten bei Lanes jede 15 sec

∞ 10 5 3,3 2,5 2

8/20

Problem

6

7

8

9

10

11

12

13

14

15

Lane 2

Lane 3

1

2

3

4

5

Lane 1

Dienst ankündigen

Dienst suchen

Dienstsucheerfolglos

Dienst nicht gefunden

9/20

Grundgedanken

• Lane-Funktionalität hängt von der Kooperation jedes Gerätes ab

• Geräte sind autonom und treffen die Kooperationsentscheidung selbst

• Unkooperatives Verhalten, um Ressourcen zu schonen (Batterie, Netzwerkressourcen)

Ziel: Anreiz, um die Kooperation zu stimulieren

Definition: Prinzipal-Agent Transaktion

PrinzipalAgent

Aktion

Belohnung

10/20

Muster von vorteilhaften Fehlverhalten

VorteilhaftesFehlverhalten

Login-Algorithmusignorieren

Keine Angebotemachen

Dienste nichtvergleichen

Dienste nichtlokal speichern

Dienste die nichtexistieren,

ankündigen

Nicht Laneerkennbar

Vortäuschen

Accept, Inform,Confirm nicht

weiter bearbeiten

Keine Spalten-nachricht senden

Keine Anfragensenden

Spalten-nachrichten

Intra Lane

Nicht weiterleiten

Ping Zähler

Such-nachrichten

Ankündigungs-nachrichten

Intra LaneInter Lane

Verändern

PassivAktiv

Lane erkennbar

Inter Lane


Such-nachrichten

AktivPassiv

11/20

Wahrnehmbarkeitsmechanismen

Lane erkennbaresaktives Verhalten

ZusätzlicheMechanismen

Mitglieder-Kooperation

Wahrnehmbarkeitsmechanismen

Nicht Lane erkennbarespassives Verhalten

Nicht Lane erkennbaresaktives Verhalten

Lane erkennbarespassives Verhalten

Sig

nie

ren

Bestätig

ungen D

ienst

e t

est

en

Sem

antik, B

eobach

ten

Suchnachrichten verändern

Suchnachrichtennicht weiterleiten

Dienste die nichtexistieren, ankündigen

Suchende Dienste nicht vergleichen

12/20








ankündigen

Nicht Laneerkennbar

Vortäuschen


weiter bearbeiten



Spalten-nachrichten

Intra Lane

Nicht weiterleiten

Ping Zähler

Such-nachrichten



Verändern

PassivAktiv

Lane erkennbar

Inter Lane


Such-nachrichten

AktivPassiv

Signieren

Bestätigungen

Semantik, Beobachten

Dienstetesten

13/20

Existierende Anreizmuster

großkleinmittelkleinAufwand

o+−− −Skalierbarkeit

o+−

keineDurchsetzbarkeitder Belohnung

Art der Belohnung

Tausch-handels-muster

wertpapierbasiert(Eigenwechselmuster)

Gemein-schafts-muster

Kollektiv-muster

EigenwechselGegen-leistung

Reputation

asymmetrischsymmetrischasymmetrischRollen

handelsbasiertvertrauensbasiertAnreiz-muster

Eigenschaften

großkleinmittelkleinAufwand

o+−− −Skalierbarkeit

o+−

keineDurchsetzbarkeitder Belohnung

Art der Belohnung

Tausch-handels-muster

wertpapierbasiert(Eigenwechselmuster)

Gemein-schafts-muster

Kollektiv-muster

EigenwechselGegen-leistung

Reputation

asymmetrischsymmetrischasymmetrischRollen

handelsbasiertvertrauensbasiertAnreiz-muster

Eigenschaften

Philipp Obreiter, Jens NimisA Taxonomy of Incentive Patterns - The Design Space of Incentives for Cooperation 2nd Workshop on Agents and Peer-to-Peer Computing (AP2PC'03), Melbourne

14/20

Von Lanes zu SLanes: Diestsuche

Lane 1

Lane 2

Lane 3Prinzipa

lAgent 2Agent 1

Kontrolliert die Signatur des PrinzipalsFragt das RepSys

Sucht Dienst erfolglos

Signiert orig. Nachricht

Kontrolliert Sign.

Fragt RepSys

Suche erfolgreich

Signiert Such-Nachricht

Sign. Quittung

Sign. Antwort

Inform. RepSysSigniert Bestätigung

Kontrolliert Signatur

Signiert Eigenwechsel

Kontrolliert Signatur

Signiert Eigenwechsel

Inform. RepSys

Inform. RepSys

Inform RepSys

Inform RepSys.

Inform RepSys.

Tradeoff 1

Lanes

Tradeoff 2

Tradeoff 3

Tradeoff 4

# Nachrichten

367

15/20

Evaluierung

• Durchgeführt mit Netzsimulator DIANEmu• Ziele der Evaluierung: - Gesamtnutzen-Gesamtaufwand - Fairness Korrelation von Individualnutzen-Individualaufwand

• Vorgehensweise:

- Parameter: 1. Heterogenität der Populationen

(Altruistische, rationale kooperative, rationale unkooperative Geräte)

2. Anzahl der durchgeführten Suchvorgänge 3. Max. Anzahl der Eigenwechsel (Kredit)

- Gemessene Werte: 1. Nutzen: gefundene Dienste 2. Aufwand: Anzahl der gesendeten

Nachrichten und der durchgeführten Vergleiche

- Einstellungen: 20 Geräte, jedes Gerät bietet genau einen

Dienst, gleichverteilte 4400 Dienstsuchen, Reputationssystem von Stefan Fähnrich.

16/20

Gesamtnutzen-Gesamtaufwand

4400 4400

2444 2382

1561 1514

874522

0

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

13745

1850119882

1348012496

18142

1594616222

0

5000

10000

15000

20000

25000

15 Kooperative 5 Unkooperative

20 Altruistische

6600 6600

8010

63306699

4909

6524

4639

0

1000

2000

3000

4000

5000

6000

7000

8000

9000

Gesa

mtn

utz

en

Nach

rich

ten

Verg

leic

he

LanesSLanes



Gesa

mta

ufw

and

Gesa

mta

ufw

and

Max. 10 Eigenwechsel

17/20

0

20

40

60

80

100

120

140

160

180

0 100 200 300 400 500

Kooperative Unkooperative

Fairness: Korrelationskoeffizient und Regressionsgerade

0

20

40

60

80

100

120

140

160

0 200 400 600 800

Kooperative Unkooperative

Aus Messungen abgeleitete Werte: 1. Korrelationskoeffizient r (Findungen-Vergleiche)

Ind

ivid

ualn

utz

en [

Findun

gen]

Individualaufwand [Vergleiche]

r=-0,18

r=0,69

#Findungen

#Vergleiche

Ind

ivid

ualn

utz

en [

Findun

gen]

Individualaufwand [Vergleiche]

2. Steigung der Regressionsgerade (b)

b=0,54

Einstellungen: 4400 Suchen, 15 Kooperative, 5 Unkooperative

Lanes SLanes

18/20

-1,0

-0,5

0,0

0,5

1,0

-0,4

-0,2

0,0

0,2

0,4

0,6

0,8

1,0

-1,0

-0,5

0,0

0,5

1,0

1,5

Fairness Betrachtung

max. Eigenwechsel-Kredit 2


Korr

ela

tionsk

oeffi

zient

Korr

ela

tionsk

oeffi

zient

Korr

ela

tionsk

oeffi

zient

b=0,81 b=1,55

b=0,25 b=0,81

b=1,9

b=0,54 b=0,81 b=0,55

max. Eigenwechsel-Kredit 10



2400 Suchen 4400 Suchen 9200 Suchen

10

Koopera

tive

10

U

nko

opera

tive

10

Koopera

tive

10

U

nko

opera

tive

44

00

Such

en

Parameter:

1. Wechselkredit

2. Population

3. Lauflänge

0,81

0,77

0,82

0,69

0,77

0,76

0,77

0,86

LanesSLanes

19/20

Zusammenfassung - Ausblick

• Lanes in Szenarien mit mäßiger Dynamik besser als Fluten

• Autonome Geräte erzielen Vorteile durch das Fehlverhalten

• Anreizschema für die Lanes-Struktur entworfen

- Gemeischaftsmuster und Eigenwechselmuster geeignet

- Adaption der Algorithmen um die Wahrnehmbarkeit zu erhöhen

• Evaluationsergebnisse

- Bei SLanes weniger Gesamtnutzen und Gesamtaufwand - Fairness erreicht da Individualnutzen und Individualaufwand gut korrelieren• Ziel erreicht: kooperatives Verhalten ist motiviert

Ausblick: Erweiterung der Lanes-Algorithmen, mehr Testfälle, andere Parametrisierung, Fine Tuning der Einstellungen!

20/20

Vielen Dank für die Aufmerksamkeit!

Fragen???

21/20

Existierende Anreizmuster

Kollektivmuster

HandelsbasierteVertrauensbasierte

Anreizmuster

WertpapiermusterTauschhandelmusterGemeinschaftsmuster

stat

isch

dynamisch

sofo

rt

versprochen

Ver

trau

en s

tim

ulie

rt

Die

snan

gebo

te

Gegenleistung stim

uliert Diensangebote

22/20

Unkooperatives Verhalten

• Eigensinniges Verhalten:Verschafft eigene Vorteile, schont eigene Ressourcen

• Verschwenderisches Verhalten:Nutzung von Ressourcen anderer Teilnehmer, schont eigene Ressourcen

• Bösartiges Verhalten:Schadet andere Teilnehmer, ohne eigene Vorteile

• Entschuldbares Verhalten:Wegen Ressourcen Mangels

23/20



Nicht Laneerkennbar

Lane erkennbar


weiter bearbeiten


Spalten-nachrichten

Intra Lane

Nicht weiterleiten

Ping Zähler

Such-nachrichten



Verändern

PassivAktiv

Inter Lane


Such-nachrichten

PassivAktiv


Nicht Laneerkennbar

Lane erkennbar

PassivAktiv PassivAktiv


ankündigen

Vortäuschen






24/20

Erweiterung der Dienstsuche

Prinzipal Agent 1

Lane 2

Lane 3

Lane 1

Agent 2

Prinzipal:

1. Signiert Such-Nachricht2. Sendet Nachricht an

Agenten 1

15. Kontrolliert die Signatur des

Agenten 2 und informiert das

Reputationssystem16. Sendet signierten Eigenwechsel an Agenten

217. Kontrolliert die Signatur

des Agenten 1 und informiert

das Reputationssystem18. Sendet signierten Eigenwechsel an Agenten

1

2

13

7

Agent 1:

3. Kontrolliert die Signatur des

Prinzipals4. Fragt das RepSys5. Sucht den Dienst erfolglos6.Signiert originale Nachricht

mit eigener Signatur7. Sendet Nachricht an

Agenten 2

14. Bekommt die Quittung, informiert das RepSys und sendet signierte

Bestätigung an Prinzipal

Agent 2:

8. Schritt 39. Informiert das RepSys10. Fragt das RepSys11. Sucht und findet den

Dienst12. Signiert eine Quittung

und sendet sie an Agenten 113. Sendet signierte

Nachricht mit dem Anbieter an

Prinzipal

12

14

18

16

#Nachrichten=7

25/20

Dienstsuche-Beispiel

Prinzipal Agent 1

Lane 2

Lane 3

Lane 1

Agent 2

Agent 1:

2. Sucht den Dienst erfolglos

3.Sendet Nachricht an Agent 2

Prinzipal:

1. Sendet Nachricht an Agent 1

Agent 2:

4. Sucht und findet den Dienst

5. Sendet Nachricht mit dem Anbieter an Prinzipal

1

3

2

#Nachrichten=3

26/20

Erweiterung der Dienstsuche

Prinzipal Agent 1

Lane 2

Lane 3

Lane 1

Agent 2

2

13

7

12

14

16

#Nachrichten=6

1. Signiert Such-Nachricht

2. Sendet Nachricht an Agenten 1

15. Kontrolliert die Signatur des Agenten 2 und informiert das RepSys

Prinzipal:

17. Kontrolliert die Signatur des Agenten 1 und informiert das Reputationssystem

16. Sendet signierten Eigenwechsel an Agenten 2

3. Kontrolliert die Signatur des Prinzipals4. Fragt das RepSys

5. Sucht den Dienst erfolglos

7. Sendet Nachricht an Agenten 2

6.Signiert originale Nachricht mit eigener Signatur

14. Bekommt die Quittung, informiert das RepSys und sendet signierte Bestätigung an Prinzipal

12. Signiert eine Quittung und sendet sie an Agenten 113. Sendet signierte Nachricht mit dem Anbieter an Prinzipal

11. Sucht und findet den Dienst

10. Fragt das RepSys

9. Informiert das RepSys8. Schritt 3

Agent 1: Agent 2:

27/20

Evaluierung

• Durchgeführt mit Netzsimulator DIANEmu• Ziele der Evaluierung: - Fairness Korrelation von Individualnutzen-Individualaufwand

und von Gesamtnutzen-Gesamtaufwand • Vorgehensweise:

– Parameter: 1. Heterogenität der Populationen

(Altruistische, rationale kooperative, rationale unkooperative Geräte)

2. Anzahl der durchgeführten Suchvorgängen

3. Max. Anzahl der Eigenwechsel– Gemessene Werte:

1. Nutzen: gefundene Dienste 2. Aufwand: Anzahl der gesendeten

Nachrichten und der durchgeführten Vergleiche

– Abgeleitete Werte: 1. Korrelationskoeffizient (Nutzen-Vergleiche) 2. Steigung der Regressionsgerade (b)

Documents

1/20 S-Lanes - Ein schlankes Overlay zur motivierten Dienstvermittlung in mobilen Ad-hoc-Netzen Universität Karlsruhe Diplomarbeit von Georgios Papadopoulos