Budapesti M szaki és Gazdaságtudományi Egyetem

Budapesti M¶szaki és Gazdaságtudományi Egyetem

Spontán kooperáció kialakulásának vizsgálata különböz® fennhatóság alá tartozó szenzorhálózatok között A közös bázisállomás esete

Schaer Péter

Konzulens: Buttyán Levente

Budapest, 2005.

Feladatkiírás A közeljöv®ben várható az olcsó, miniat¶r szenzorok és az azokból felépül® többugrásos hálózatok elterjedése. Az ilyen jelleg¶ szenzorhálózatok egyik legfontosabb tervezési kritériuma a szenzorok élettartamának maximalizálása, hiszen a legtöbb alkalmazásban a szenzorok akkumulátorának újratöltése vagy cseréje praktikusan vagy egyáltalán nem lehetséges. Az utóbbi években számos protokollt javasoltak a szenzorhálózatokban történ® kommunikációra. Ezek a munkák azonban azzal az alapfeltevéssel éltek, hogy az összes szenzort egy cég vagy hatóság tartja ellen®rzése alatt. Ésszer¶ a feltevés, hogy a gyakorlatban számos ilyen, különböz® fennhatóság alatt álló hálózat fog egyazon földrajzi helyen megjelenni. Még ha a szenzorok különböz® irányítás alatt is állnak és különböz® feladatokat látnak is el, a közöttük lév® kommunikációs csatlakozási felület lehet ugyanaz és ez lehet®séget ad kooperáció kialakulására, mely tovább növelheti a hálózatok élettartamát. A játékelmélet módszereit használva vizsgálja meg a kooperáció kialakulásának feltételeit a különböz® fennhatóság alá tartozó szenzorhálózatok között!

• Deniáljon alkalmas modellt a probléma vizsgálatára azon feltevés mellett, hogy az összes hálózat egy közös bázisállomást használ! • A deniált modellben vegye gyelembe, hogy a hálózatok els®dleges feladata a mért adatok eljuttatása a bázisállomás(ok)hoz és emellett szeretnék az élettartamukat maximalizálni! • Ahol lehet, ott végezzen analítikus elemzést, ahol ezt a feladat bonyolultsága nem engedi meg, ott használjon számítógépes szimulációt! • A stratégiatér méretét alkalmas módon korlátozza, hogy a szimuláció kivitelezhet® legyen! • Összegezze tapasztalatait, s ezen összegzés alapján tegyen javaslatot arra, hogy hogyan lehet a kooperáció feltételeinek kialakulását el®segíteni a rendszerben! • Elemezze az irodalomban található kooperációval kapcsolatos munkákat és hasonlítsa össze velük saját eredményeit!

Nyilatkozat Alulírott, Schaer Péter, a Budapesti M¶szaki és Gazdaságtudományi Egyetem hallgatója kijelentem, hogy ezt a diplomatervet meg nem engedett segítség nélkül, saját magam készítettem, és a diplomatervben csak a megadott forrásokat használtam fel. Minden olyan részt, melyet szó szerint, vagy azonos értelemben, de átfogalmazva más forrásból átvettem, egyértelm¶en, a forrás megadásával jelöltem.

............... Schaer Péter

Tartalomjegyzék 1. Bevezetés

7

2. Szenzorok és szenzorhálózatok

10

2.1. Szenzorok zikai felépítése . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

2.2. Szenzorok rétegszerkezete

. . . . . . . . . . . . . . . . . . . . . . . . . . .

13

2.2.1. Alkalmazási réteg . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.2.2. Szállítási réteg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.2.3. Hálózati réteg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

2.2.4. Adatkapcsolati réteg . . . . . . . . . . . . . . . . . . . . . . . . . .

16

2.2.5. Fizikai réteg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.3. Szenzorhálózatok felhasználása . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.3.1. Katonai felhasználás . . . . . . . . . . . . . . . . . . . . . . . . . .

18

2.3.2. Természetben történ® felhasználás . . . . . . . . . . . . . . . . . . .

20

2.3.3. Egészségügyi alkalmazások . . . . . . . . . . . . . . . . . . . . . . .

21

2.3.4. Otthoni alkalmazások . . . . . . . . . . . . . . . . . . . . . . . . . .

22

2.3.5. Egyéb kereskedelmi felhasználások . . . . . . . . . . . . . . . . . . .

23

2.4. Szenzorhálózatok tervezési szempontjai . . . . . . . . . . . . . . . . . . . .

24

3. Csomagtovábbítás szenzorhálózatokban

28

3.1. Útválasztás . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

28

3.1.1. Útválasztási algoritmusok . . . . . . . . . . . . . . . . . . . . . . .

29

3.2. Kooperáció ösztönzéssel

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

3.2.1. Ösztönz® sémákkal szemben támasztott követelmények . . . . . . .

36

3.2.2. Ösztönz® sémák díjazási típusai . . . . . . . . . . . . . . . . . . . .

37

3.2.3. Példák számla alapú ösztönzési sémákra . . . . . . . . . . . . . . .

38

3.2.4. Példa hírnév alapú ösztönzési sémára . . . . . . . . . . . . . . . . .

42

3.3. Kooperáció ösztönzés nélkül . . . . . . . . . . . . . . . . . . . . . . . . . .

43

4. Játékelméleti eszköztár

46

4.1. Domináns stratégiák . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

46

4.2. Nashegyensúly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

4.3. Maximális Nashegyensúly . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

5. Az egyszer¶sített modell

52

5.1. A kétlépéses stratégiák . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

55

5.1.1. A kétlépéses stratégiák vizsgálati eredményei . . . . . . . . . . . . .

56

5.2. Az utolsó lépés modell . . . . . . . . . . . . . . . . . . . . . . . . . . . .

58

5.2.1. Az utolsó lépés modell vizsgálati eredményei . . . . . . . . . . . .

59

5.3. A vektorsúlyos modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

5.3.1. A vektorsúlyos modell vizsgálati eredményei . . . . . . . . . . . .

61

6. A b®vített modell

64

6.1. Vizsgálati eredmények egy bázis esetére . . . . . . . . . . . . . . . . . . . .

65

6.1.1. Szimmetrikus esetek . . . . . . . . . . . . . . . . . . . . . . . . . .

66

6.1.2. Aszimmetrikus esetek . . . . . . . . . . . . . . . . . . . . . . . . . .

68

6.2. Vizsgálati eredmények több bázis esetére . . . . . . . . . . . . . . . . . . .

70

7. A b®vített modell továbbfejlesztése 7.1. A továbbfejlesztett modell vizsgálati eredményei . . . . . . . . . . . . . . .

8. Konklúzió és továbblépési lehet®ségek

72 74

79

Kivonat A szenzorhálózatok sok résztvev®b®l álló, nagy kiterjedés¶ hálózatok, melyeket számos csomópont és néhány bázisállomás alkot. A szenzorok környezetük zikai jellemz®it mérik az érzékel®ik segítségével, mérési eredményeiket pedig a bázisállomások felé továbbítják lehet®leg több ugráson keresztül. Minthogy a szenzorok általában beépített akkumulátorról m¶ködnek, fontos tervezési szempont az élettartamuk maximalizálása. Ebben a diplomatervben különböz® fennhatóság alatt álló szenzorhálózatokat vizsgálok, amelyek azonos földrajzi helyen lettek telepítve. Ebben az esetben a szenzorok élettartamát növelni lehetne olymódon, hogy a csomópontok olyan csomagokat is továbbítanának a kooperativitás jegyében, amelyek a másik szenzorhálózattól érkeztek hozzájuk. Természetesen fennáll a veszélye, hogy egyes önz® szenzorok kihasználják a többi szenzor csomagtovábbítási hajlandóságát és saját nyereségük növelésére használják a hálózatot. Ezt a problémát vizsgálom a következ®kben játékelméleti eszközök segítségével. Megmutatom, hogy az esetek többségében érvényre jutnak a kooperatív stratégiák mindenféle küls® serkent® tényez® (pl. díjazás) nélkül is.

Abstract Sensor networks are large scale networks consisting of several nodes and some base stations. The nodes are monitoring the environment and send their measurement data towards the base stations possibly via multiple hops. Since the nodes are often battery powered, an important design criterion for sensor networks is the maximization of their lifetime. In this paper, I consider multi-domain sensor networks, by which I mean a set of sensor networks that co-exist at the same physical location but run by dierent authorities. In this setting, the lifetime of all networks can be increased if the nodes cooperate and also forward packets originating from foreign domains. There is a risk, however, that a selsh network takes advantage of the cooperativeness of the other networks and exploits them. I study this problem in a game theoretic setting, and show that, in most cases, there is a cooperative Nash equilibrium in the system, even without introducing any external incentives (e.g., payments).

1. fejezet Bevezetés A szenzorhálózatok nagy volumen¶, jellemz®en sok szenzorból álló hálózatok, melyek többnyire egy, vagy több központi elhelyezkedés¶ bázisállomás köré csoportosulnak. A szenzorhálózatok lesznek a közeljöv® leghatékonyabb felügyel® rendszerei, hiszen a rengeteg önálló, autonóm m¶ködésre képes szenzor szinte bármely zikai jellemz® mérésére felkészíthet®, akár rövidtávú mintavételezésr®l, akár hosszútávú meggyelésr®l beszélünk. Ilyen hálózatok segítségével lehet®ség nyílik majd olyan extrém körülmények monitorozására is, amire eddig nem volt lehet®ség. Nem okoznak majd problémát az eddigi érzékel®k számára elviselhetetlenül magas ill. alacsony h®mérsékleti viszonyok, de az él® szervezetek bels® folyamatainak meggyelése el®l is leomlanak az akadályok. A szenzorhálózatok valójában ad hoc hálózatok, vagyis mind a kommunikáló eszközök elhelyezkedésének tekintetében, mind az infrastruktúra tekintetében szervezetlenek m¶ködésük kezdetekor. Az ad hoc hálózatok saját maguk számára építik ki a kommunikációs linkeket, minden el®zetes információ nélkül képesek rövid id® alatt kialakítani a rendezett interakcióhoz szükséges csatornákat. Ezt a tulajdonságot önszervez® képességnek hívjuk és nagy hangsúlyt fektetünk rá, hiszen általa lehet®vé válik a központosított eszközfelügyelet kiküszöbölése és a teljesen elosztott m¶ködés megvalósítása. Megjegyzend®, hogy a szigorú értelemben vett mobil ad hoc hálózat fogalma nem fedi a szenzorhálózat fogalmát. El®bbinél ugyanis viszonylag nagyobb méret¶, nagy mobilitású, újratölthet® egységek kommunikálnak egymással, míg a szenzorhálózatoknál sokkal több, de kicsi, általában helyhez kötött és jellemz®en újra nem tölthet® akkumulátorú egység kommunikál a központi bázisállomással. Ennek ellenére gyakran fogok hivatkozni az ad hoc hálózatokra, mivel azok a szenzorhálózatok legközelebbi rokonai, ezért az ad hoc hálózatokban alkalmazott megoldá7

1. FEJEZET. BEVEZETÉS

8

sok jó alapjai lehetnek a szenzorhálózatokban alkalmazandó megoldásoknak. A közeljöv®ben kiépül® szenzorhálózatok feladata a monitorozás lesz, amit magyarul meggyelésnek mondhatnánk. A szenzorok valamilyen rendszer szerint méréseket fognak végezni és eredményeiket a bázisállomásoknak felé fogják elküldeni. Mivel a szenzorok autonóm, saját processzorral rendelkez® egységek (lényegében bizonyosfokú intelligenciával ellátott érzékel®k), lehet®ség nyílik a mérési adatok el®feldolgozására, esetleges aggregálására vagy akár a hibás adatok eldobására és új mérés indítására. A bázisállomás a szenzoroktól kapott mérési eredményeket feldolgozza, majd továbbítja azokat a felhasználó felé, esetleg visszajelzést küld a szenzoroknak a m¶velet sikerességével kapcsolatban. Ahhoz, hogy egy csomag a szenzortól eljusson a bázisállomásig, vagy komoly energiamennyiségre van szükség, vagy más szenzorok segítségére. Az els® esetben a szenzor közvetlenül a bázisállomásnak küldi a csomagját, ami ugyan biztosan meg fog érkezni, viszont hatványozottan több energiát emészt fel a kommunikáció, mint a második esetben, amikor a szenzorok egymást segítve küldik a csomagokat. Ha több szenzorhálózatot telepítenek földrajzilag azonos helyre, akkor azok képesek lehetnek egymás csomagjait a leírt módon továbbítani. Természetesen utóbbi esetben el®fordulhat, hogy a bázishoz vezet® úton valamelyik szenzor önz® és nem hajlandó a csomagot továbbítani, ezzel is spórolva sz¶kös er®forrás-készleteivel. A szakirodalomban számos ösztönz® sémát javasolnak a kutatók, amivel az ilyen önz® viselkedés kiküszöbölhet®. Sajnos ezek a sémák komoly extra ráfordítással járnak (ún. overheaddel), hiszen az összes szenzornak be kell tartania a keretrendszer diktálta szabályokat. Egy ilyen környezetben, ahol az er®források amúgy is sz¶kösek, er®sen meggondolandó, milyen serkent® módszert alkalmazunk. Ebben a dolgozatban arra szeretnék rámutatni, hogy ezekre az ösztönz® sémákra gyakran nincs is szükség! A szenzorhálózat paramétereinek megfelel® megválasztásával küls® serkentés nélkül is kialakul az esetek többségében a kooperáció! Ezt nevezzük spontán kooperációnak. Egy racionális viselkedés¶ szenzor nyilván csak akkor fogja a többi szenzor csomagjait továbbítani, ha az neki is megéri. Nem beszélhetünk ugyan közvetlen megtérülésr®l, ugyanakkor hosszú távon kizet®dik a kooperáció, hiszen a szenzorok élettartama a kisebb energiafogyasztás miatt n®, ami els®dleges cél az olyan rendszereknél, amelyeknél az akkumulátorok cseréje praktikusan nem megoldható vagy eleve lehetetlen. Kooperáció alatt tehát a csomagtovábbításban történ® segítségnyújtást értjük, a spontán kooperáció ezen segítsgényújtás önérdekre alapozott megjelenési formája. A diplomaterv az alábbiak szerint épül fel. A 2. fejezetben a szenzorok zikai és logi-

1. FEJEZET. BEVEZETÉS

9

kai felépítésér®l lesz szó, valamint a szenzorhálózatok tervezési szempontjairól és felhasználásáról. A 3. fejezetben áttekintést adok az ad hoc hálózatokban és a szenzorhálózatokban alkalmazott útválasztási megoldásokról és részletezem a szakirodalomban fellelhet® ösztönz® sémák elveit és megoldásait, valamint bevezetem a spontán kooperáció fogalmát. Az felhasznált játékelméleti fogalmakat deniálom a 4. fejezetben. A problémát egy egyszer¶sített modell segítségével az 5. fejezetben formalizálom és kezdem el vizsgálni. A 6. fejezetben egy sokkal általánosabb modellen folytatom a vizsgálatokat, ami már jóval közelebb áll a való életben el®forduló hálózatokhoz. A 7. fejezetben bemutatom az általam használt legkinomultabb modellt és egyben egy másfajta értelmezés szerint is vizsgálom a spontán kooperáció kialakulását. Végül a 8. fejezetben összefoglalom az eredményeimet és felvázolok néhány kecsegtet® továbblépési lehet®séget a témával kapcsolatban.

2. fejezet Szenzorok és szenzorhálózatok Az utóbbi évek mikro-elektronikai fejlesztései lehet®vé tették olyan miniat¶r eszközök kidolgozását, melyek képesek a környezetük meggyelésére, ún. monitorozásra. Ezeket az olcsó, a m¶ködésükhöz kevés energiát igényl®, ugyanakkor intelligens eszközöket nevezzük szenzoroknak. Az angol sensor szónak ugyan van magyar megfelel®je, az érzékel®, viszont ez utóbbit egyszer¶bb eszközök megnevezésére használjuk, amelyek ténylegesen csak érzékelni képesek valamilyen zikai jellemz®t. A diplomaterv szóhasználatában ezentúl a szenzor kifejezést fogom alkalmazni, jelezve ezzel, hogy jelen esetben nem egyszer¶ mér®eszközökr®l, hanem mikroprocesszorral és saját energiaforrással ellátott, autonóm berendezésekr®l van szó. A szenzor szinonímája a csomópont. A szenzorok megszületése életre hívta a szenzorhálózat fogalmát, ami alatt szenzorok egymással kommunikáló halmazát értjük. Várhatóan e szenzorhálózatok lesznek a közeljöv® leghatékonyabb környezet-meggyel® eszközei.

2.1. Szenzorok zikai felépítése A szenzorok legáltalánosabb felépítését a 2.1. ábra szemlélteti [2]. A négy f® egységet folytonos vonallal rajzolt téglalapok jelölik, az opcionális egységek és összeköttetéseik szaggatott vonalakkal kerültek megrajzolásra.

- Az érzékel® egység két további részre bontható: magára az érzékel®re és az analóg digitális átalakítóra (A/D). A zikai jellemz®k megváltozását az érzékel® érzékeli és

10

2. FEJEZET. SZENZOROK ÉS SZENZORHÁLÓZATOK

Helymeghatározó egység Érzékelõ egység Érzékelõ A/D

11

Mozgató egység

Feldolgozó egység Processzor Tároló

Kommunikációs egység

Akkumulátor

Energiafejlesztõ egység

2.1. ábra. Szenzor felépítése analóg jeleket bocsát ki. Ezeket az analóg jeleket az analógdigitális átalakító digitális jelekké transzformálja, majd továbbítja a feldolgozó egységnek. - A feldolgozó egység szintén két részb®l áll: magából a mikroprocesszorból, amely a számítási feladatok elvégzéséért és a szenzor vezérléséért felel®s, valamint egy kisebb tárolóból, amelyben a szenzor m¶ködéséhez szükséges információk, ill. esetleg néhány mérési eredmény található. Annak ellenére, hogy jelent®s fejl®dés tapasztalható a miniat¶r processzorok teljesítménye terén, a szenzorok igényeinek kielégítése még mindig komoly kihívást jelent. A Berkeley Egyetemen fejlesztett Smart Dust szenzor [4] 4 MHz-es Atmel AVR 8535 típusú mikrokontrollert, 8 KB-os parancsmemóriát, 512 byte-os RAM és szintén 512 byte-os EEPROM modulokat tartalmaz. A processzoron TinyOS operációs rendszer fut, ami 3500 byte tárolóterületet igényel. Emellett 4500 byte-nyi szabad tárolókapacitás áll rendelkezésre. - A kommunikációs egység felel®s a szenzorok közötti kommunikáció megvalósításáért. Ez lehet aktív vagy passzív optikai eszköz (ahogy a Smart Dust szenzorokban) vagy rádiófrekvenciás interfész. Utóbbi megvalósítása jóval komplexebb áramköröket igényel, ami egyben a szenzor árát is negatívan befolyásolja. Mindazonáltal a kutatások


12

többségében rádiófrekvenciás kommunikációt feltételeznek a szerz®k, mert a csomagméretek kicsik és az adatforgalom is moderált, valamint a rádiófrekvenciás adattovábbítás sokkal robosztusabb, mint az optikai alapú, hiszen utóbbinál a szenzorok helyzete is befolyásoló tényez®. A kell®en energiatakarékos rádiós interfész kifejlesztése egyel®re várat magára, a jelenleg használt megoldások sajnos nem alkalmazhatóak, mert nem elég hatékonyak. Példaként említhetjük a Bluetooth-nál alkalmazott eljárást, aminek a hibája az, hogy ki- ill. bekapcsolgatja a kommunikációs hardvert, ami nagyon sok energiát fogyaszt. - A szenzorok számunkra legfontosabb egysége az akkumulátor, amely a szenzor m¶ködéséhez szükséges energiát biztosítja és véges er®forrásnak számít. Minthogy a szenzorok a lehelyezésük után gyakran nem hozzáférhet®ek, élettartamukat általában az akkumulátorukban tárolható energia mennyisége szabja meg. Ez például egy Smart Dust szenzor esetén 1 J nagyságrendjébe esik. - Az opcionális komponensek közül kezdjük a felsorolást az energiafejleszt® egységgel. Már folynak a kutatások abban az irányban, hogy a szenzorok akkumulátorainak csekély élettartamát meghosszabbítsák azáltal, hogy a környezetb®l nyernek energiát (energy scavenging ill. energy harvesting). Ennek legegyszer¶bb példája a szenzorok felszerelése napelemmel. - Számos útválasztó és érzékel® feladat megköveteli, hogy a szenzor tisztában legyen saját pozíciójával. Ennek meghatározására szolgál a helymeghatározó egység. Ez lehet például GPS (Global Positioning System, Globális Helymeghatározó Rendszer), ami már 5 m-nél kisebb pontatlanságot garantál. Sajnálatos módon az összes szenzor felszerelése GPS-szel rendkívül megemelné azok árát. Áthidaló megoldás lehet, ha csak a csomópontok egy részét szereljük fel GPS-szel és a többi szenzor ezek segítségével határozza meg a pozícióját. - A mozgató egység segítségével a szenzor képes megváltoztatni a helyét. Ezt az egységet olyan esetekben érdemes a szenzorra szerelni, amikor a szenzor pozíciója dönt® fontosságú a mérés elvégzésének sikeressége kapcsán. Mindezen egységeknek, vagyis az egész szenzornak nagyon kicsinek kell lennie. A szakma jelenleg az 1 cm3 alatti mérettartományt preferálja, a rövidtávú cél az 1 mm3 -es tartomány elérése. Hasonlóan er®s kritériumoknak kell egy szenzornak megfelelnie a súlya


13

tekintetében is. A cél az, hogy a szenzorok súlya annyira lecsökkenjen, hogy azok lebegni tudjanak a leveg®ben!

2.2. Szenzorok rétegszerkezete A szenzorhálózatokban mind a szenzorok, mind a bázisok azonos elven épülnek fel. A 2.2. ábra szemlélteti a szenzorokban alkalmazott legbonyolultabb rétegszerkezetet [2]. Ennél gyakran találkozunk egyszer¶bb megoldásokkal is.

Adatkapcsolati réteg

Feladatütemezõ sík

Hálózati réteg

Erõforráskezelési sík

Szállítási réteg

Mobilitás menedzsement sík

Alkalmazási réteg

Fizikai réteg

2.2. ábra. Szenzorok logikai rétegszerkezete

A mérési feladattól függ®en különböz® alkalmazói szoftver található az alkalmazási rétegben. A szállítási réteg feladata a szenzorhálózatban áramló adatfolyamok karbantartása. A hálózati réteg felel®s a szállítási rétegt®l kapott adatok útválasztásáért. A közegelérési alrétegre, ami az adatkapcsolati rétegben helyezkedik el, nagy felel®sség hárul a m¶ködési környezet zajossága és a szenzorok mobilitása miatt, mivel nagyon energiatakarékosnak kell lennie és képesnek az ütközések minél nagyobb arányú elkerülésére. A


14

zikai réteg az egyszer¶, de robosztus modulációért, adattovábbításért és adatfogadásért felel. A csomópontok három síkja, az er®forráskezelési-, mobilitás-menedzsment- és feladatütemez® síkok felel®sek az er®források felügyeléséért, a szenzor mozgásának gyelésért és a feladatok ütemezéséért. Az er®forráskezelési sík menedzseli a szenzor energiafelhasználását. Például a szenzor kikapcsolhatja a vev®készülékét egy csomag érkezése után, hogy ezzel elkerülje a duplikátumok megkapását és energiát spóroljon. Hasonlóképpen elképzelhet®, hogy a szenzor broadcast üzenetet küld a szomszédainak, ha alacsony már az energiaszintje, hogy ezentúl nem fog tudni résztvenni az útválasztási algoritmusokban és nem fogja a többi szenzor csomagját továbbítani, a továbbiakban csak méréseket végez. A mobilitásmenedzsment réteg gyelemmel kíséri a szenzor mozgását, így mindig naprakészen tudja tartani a bázisállomáshoz vezet® utat és a szenzorok mindig tudják, mely csomópontok az aktuális szomszédaik. A feladatütemez® sík kiegyenlíti és ütemezi a mérési feladatok elvégzését. A kiegyenlítés arra utal, hogy egy adott régióban nem minden szenzornak kell elvégeznie az adott feladatot: ha valamelyik csomópont energiaszintje alacsonyabb, akkor felmentést kaphat ez alól, ha egy másik szenzor hajlandó és képes több mérést végezni. Természetesen ez már egy magasabb tudású szenzorhálózatnak lehet csak a sajátja, általános esetben azt feltételezzük, hogy a feladatokat a szenzorok önállóan végzik el, együttm¶ködés csak a mérés után történik, úgymint az utófeldolgozásban és az adattovábbításban.

2.2.1. Alkalmazási réteg Annak ellenére, hogy a szenzorhálózatoknak számos felhasználási módja ismert (lsd. 2.3. fejezet), az alkalmazási rétegbeli protokollok kutatási területe még jókora fehér folt. Elképzelhet® például menedzsment jelleg¶ protokollok kidolgozása, melyek képesek lennének az alacsonyabb szint¶ szoftverrétegeket és a hardvert elfedni a felhasználók el®l, biztosítva ezzel a széleskör¶ felhasználás lehet®ségét. Hasonlóképpen szükség lenne olyan protokollokra, melyek partícionálni tudnák a hálózatot akár helyileg, akár a mérés típusának szempontjából, hogy egy-egy mérést ne kelljen minden csomópontnak elvégezni, csak azoknak, amelyek adataira valóban szükség van az aggregáció ill. a kiértékelés során. Az alkalmazási rétegbeli protokolloknak a következ® feladatokat kellene ellátniuk. - mérés, érzékelés - együttm¶ködés a helymeghatározó eszközökkel


15

- óraszinkronizáció - szenzorok mozgatása - szenzorok be- és kikapcsolása - a hálózat gyelése és esetleges újrakongurálása - hitelesítés, kulcskiosztás, biztonságos adatcsere - szenzorok összehangolása

2.2.2. Szállítási réteg A szállítási rétegre els®sorban akkor van szükség, ha a szenzorhálózatunkat el akarjuk érni küls® hálózatból is, pl. az interneten keresztül. Egyel®re a szenzorok szállítási rétegér®l is hasonló mondható el, mint az alkalmazási rétegr®l, vagyis nem sok kutatási eredmény kapcsolható hozzá. A jelenlegi elképzelések szerint a küls® hálózati elérést TCP/UDP protokollal lehetne megvalósítani, ami a bázisállomás és az internet közötti adatforgalmat irányítaná. A bázis és a szenzorok között pedig valamilyen UDP jelleg¶ protokollal folyhatna a kommunikáció. Számos megkötéssel kell azonban számolni (lsd. 2.4. fejezet), így a szenzorhálózatok szállítási rétegében alkalmazott protokollok kifejlesztése továbbra is kihívásokkal teli feladat.

2.2.3. Hálózati réteg A hálózati réteg feladata a csomagok (mérési eredmények vagy aggregált adatok) eljuttatása a forrástól a célig. Ha több úton is lehet®ség van a továbbításra, akkor a hálózati réteg választja ki a felhasználandót. A útválasztásról (routingról) b®vebben a 3. fejezetben lesz szó. A hálózati réteg másik fontos feladata a más hálózatokkal való együttm¶ködési képesség biztosítása. Más hálózat alatt érthetünk más szenzorhálózatokat vagy az internetet is. Ilyenkor a bázisállomások vagy átjáróként szolgálnak a hálózatok között, vagy közösen kiépítenek egy gerinchálózatot, amihez a küls® hálózatok egy átjárón keresztül csatlakozhatnak. A szenzorhálózatok csomópontjainak fontos tulajdonsága az a moderált számítási kapacitás, amit a rájuk integrált processzorok tesznek elérhet®vé. Ezáltal lehet®ség nyílik a


16

hálózat által mért adatok el®feldolgozására ill. aggregálására [5]. Ez utóbbi technika egyike azon területeknek, amelyeknél még több a kérdés, mint a válasz. Maga az aggregálás, mint technika arra utal, hogy az azonos attribútumú adatokat (pl. az közelít®leg azonos helyr®l származó h®mérsékleti értékeket) érdemes egy vizsgálat után egybeolvasztani (pl. medián képzéssel), mert így már korán kiderülhetnek a mérési hibák és jelent®sen csökkenhet az adatforgalom. Az aggregáció lehet®ségének megteremtése szintén a hálózati réteg feladata.

2.2.4. Adatkapcsolati réteg Az adatkapcsolati réteg felel®s az adatfolyamok multiplexálásáért, a kommunikációs közeg eléréséért és a hibajavításért. Pont-pont vagy pont-multipont kapcsolatot biztosít a kommunikációs hálózatban. Az adatkapcsolati réteg legfontosabb része a közegelérési alréteg, a MAC (Medium Access Control). A MAC alrétegnek egy vezetéknélküli, többugrásos, önrendez® hálózatban két célt kell elérnie. Egyrészt meg kell teremtenie a hálózat infrastruktúráját. Mivel rengeteg csomópont van egymás mellé lehelyezve egymástól függetlenül, a MAC alrétegnek ki kell építenie a kommunikációs kapcsolatokat, vagyis az adatutakat. Másrészt fair módon és hatékonyan kell megosztania a kommunikációs közeg adta er®forrásokat a szenzorok között. Sajnos a jelenleg használt MAC protokollok nem alkalmasak közvetlenül szenzorhálózatokban, mivel például a celluláris hálózatok teljesen más topológiával rendelkeznek (a bázisok ott vezetékkel vannak összekötve és minden csomópont közvetlenül az aktuális bázissal kommunikál), a Bluetooth-hoz hasonló piconetek pedig maximum 8 résztvev®b®l állhatnak, vagyis nagyságrendekkel kisebbek, mint a szenzorhálózatok. Ugyanakkor az egy szenzor által áthidalható kommunikációs távolság lényegesen kisebb, mint általában a piconeteknél. Fontos kérdés itt is az energiatakarékosság. A legelterjedtebb energiaspórolási módszer a rádió adó-vev® kikapcsolása a nyugalmi fázisokban. Azonban nem szabad elfelejteni, hogy a szenzorok általában rövid adatcsomagokat küldenek, ezáltal egy-egy bekapcsolással csak kevés adat továbbítódik. Ez azt jelenti, hogy az egy csomagra es® energia (vagyis az elhasznált energia és a hasznos elküldött csomagok számának hányadosa) annyira megnövekedhet, hogy jobban járnánk, ha végig bekapcsolva tartanánk az adó-vev®t. Ez tehát egy újabb mérlegelend® szempont adatkapcsolati rétegbeli protokollok tervezésénél. A hibajavítás szintén fontos képesség a szenzorhálózatoknál, mivel a környezeti fel-


17

tételek gyakran mostohák, így a sugárzott információk nagy eséllyel módosulhatnak. A szenzorhálózatokkal kapcsolatos kutatások egyel®re csak a konvolúciós kódolókat vizsgálták, a többi hibajavító séma egyel®re nem került górcs® alá.

2.2.5. Fizikai réteg A zikai réteg feladatai közé tartozik a frekvenciaválasztás, a viv®frekvencia-generálás, a jeldetekció, a moduláció és a titkosítás. A frekvenciaválasztásról a 2.4. fejezetben fogok b®vebben írni. A viv®frekvencia-generálás és a jeldetekció hardverközeli fogalmak és els®sorban a rádió adó-vev® tervezésével függenek össze, ezért ebben az alfejezetben inkább a jelterjedési problémákra és az energiatakarékosságra koncentrálok. Ismert tény, hogy a nagy távolságú vezetéknélküli kommunikáció nagyon drága lehet mind az energiafogyasztás, mind az eszközök szükséges komplexitása miatt. Általánosságban elmondhatjuk, hogy egy jel d távolságra továbbítása dα -val arányos nagyságú energiamennyiséget igényel, ahol α a környezetre jellemz® energiafogyasztási tényez® (2 ≤ α ≤ 5). Az α értéke nyílt terepen 2 körüli, épületekben akár 5 is lehet. Megjegyzend®, hogy a talajhoz közel elhelyezked® antennák esetén α értéke jellemz®en 3, vagyis a szenzorhálózatokban is ezzel az értékkel érdemes kalkulálni. Az energiafogyasztás azonban nem csak e távolságfügg® komponensb®l áll, hanem tartozik hozzá egy állandó tag, amely a csatornához való kapcsolódás költségét szimbolizálja. Ez alapján a csomagküldés energiaigénye: Esend = dα + Ef ix . A csomagfogadással kapcsolatban elmondható, hogy annak energiaigénye szintén jelent®s, a legfrissebb kutatások szerint összemérhet® a küldés energiaigényével. Ezekb®l adódóan törekedni kell a szenzorhálózatokban a többugrásos kapcsolatok kialakítására, hiszen azzal az egy csomagra jutó energiafogyasztás drasztikusan lecsökkenthet®. Ha egy csomag továbbításában ezen elvet követve több szenzor is résztvesz, azok összes ráfordított energiája is szignikánsan kevesebb annál, mintha a forrás csomópont közvetlenül a bázisállomással kommunikált volna.

2.3. Szenzorhálózatok felhasználása A szenzorhálózatok általában számos különböz® tulajdonságú, más zikai jellemz®t mér® szenzorokból épülnek fel. Gondoljunk csak például arra, mennyi mindent lehet egyszer¶ érzékel®kkel mérni! Alkalmazhatunk szeizmológiai, mágneses er®teret mér®, h®mérsékletet,


18

fényer®sséget vagy hangnyomást mér® szenzorokat, de a sort még hosszan folytathatnám. Ezen szenzorokból például a következ® monitorozó rendszerek építhet®k ki: - gépjárm¶vek mozgásának gyelése - fényviszonyok koordinálása épületen belül - objektumok jelenlétének ill. hiányának észlelése - különböz® testeket ér® mechanikai hatások feltérképezése - h®mérsékleti viszonyok szabályozása épületen belül - katonai jelleg¶ meggyelés - él® testen belüli folyamatok vizsgálata A következ® alfejezetekben kicsit b®vebb áttekintést adok a szenzorhálózatok felhasználásának ma ismert területeir®l. A felhasználási formákat katonai, természeti, egészségügyi, otthoni és egyéb kereskedelmi kategóriákba soroltam [2]. Természetesen ez a kategorizálás szubjektív, az alkalmazások más besorolása ugyanúgy elképzelhet®.

2.3.1. Katonai felhasználás A vezeték nélküli hálózatok fontos részét alkothatják a C4ISRT (command, control, communications, computing, intelligence, surveillance, reconnaissance and targeting) rendszereknek. A gyors alkalmazhatóság, önrendez® képesség és a hibat¶rés miatt a szenzorhálozatok alkalmazása nagy eredményekkel kecsegtet a C4ISRT alkalmazásokban. Tekintve, hogy a szenzorhálózatok alatt redundáns rendszereket értünk, amelynél egy-egy csomópont kiesése még nem degradálja a hálózat teljesít®képességet jelent®sen, így a katonai alkalmazásokban elvárt hibat¶rési kritériumnak kiválóan eleget tesznek. Az alábbiakban felsorolok néhány tipikus katonai alkalmazási lehet®séget.

Hadsereg és felszerelés ellen®rzése A hadsereg vezet®i állandó jelleggel nyomon tudnák követni saját csapataik ill. a felszerelés mozgását szenzorhálózatok alkalmazásával. Minden csapat vagy akár minden katona, minden felszerelés és a kritikus l®szerek is fel lehetnek szerelve miniat¶r szenzorokkal, melyek közvetítik visel®jük pozícióját egy központi állomás (bázis) felé. A csapatok ill. hadosztályok vezet®i a


19

beérkezett adatok alapján mindig aktuális képet láthatnak hadseregük állapotáról. Az adatokat tovább is lehet küldeni a fels®bbvezetéshez, esetleg közben aggregálni más földrajzi pozícióról érkez® jelentésekkel, így a hierarchia tetején lév® személyek is naprakész információkkal rendelkezhetnek.

Hadszíntér felügyelet A stratégiai fontosságú területek, utak, csomópontok gyorsan behálózhatóak szenzorhálózatokkal és így az ellenséges behatolás azonnal észlelhet®vé válik. A szenzorok alacsony ára miatt nincs szükség a már kiépített hálózatok lebontására sem, amennyiben a hadsereg mozgása miatt azok esetleg szükségtelenné válnak.

Ellenséges csapatok és területek felderítése Az egyes területeken el®re lehet szenzorhálózatokat telepíteni azzal az indokkal, hogy az ellenség odaérkezésének idejére már kiépített monitorozó rendszer álljon rendelkezésünkre. A másik lehet®ség hasonló cél elérésére az, hogy a szenzorokat kiszorhatjuk egy, az ellenség vonalai mögé berepül® gépr®l is. A szenzorok környezethez való adaptivitási képessége, autonóm m¶ködésük és az ad hoc hálózati szemlélethez igazodó tervezésük képessé teszi a szenzorokat arra, hogy ilyen extrém el®feltételek mellett is hálózatba rendez®dve fontos méréseket végezzenek.

Célzás A szenzorhálózatokat célzó ill. utólagos iránymódosító rendszerek részeként is elképzelhetjük. Így jutunk el az intelligens fegyverek fogalmához, aminek a lényege az, hogy ezek az eszközök emberi beavatkozás nélkül képesek a célt felderíteni és a támadást végrehajtani.

Hadszíntéri károk felbecsülése A szenzorhálózatok hibat¶rése megfelel® eszközzé teszi azokat olyan monitorozási célokra, ahol a hálózatot ér® hatások extrémek, pl. egy csatamez® közepén. A harc végeztével a hálózat még jó eséllyel m¶köd®képes lesz, így a károk felmérését el tudjuk vele végezni.

Nukleáris-, biológiai- és vegyi támadás észlelése és felderítése Biológiai- és vegyi támadások esetén a gyors és pontos észlelés feltétele, hogy közel legyünk ahhoz a ponthoz, ahol maga a rakéta felrobban. Ez nyilván csak hibat¶r® és er®sen ellenálló eszközökkel valósítható meg. A szenzorhálózatokat erre a célra is alkalmazhatjuk biológiai- vagy vegyi gyelmeztet® rendszerekként, használatukkal ugyanis a reakcióid® drasztikusan lecsökkenhet az észlelés pontosságának növekedése mellett, ami


20

jelent®sen csökkenti a támadás veszélyét. Nukleáris támadások esetén az emberekb®l álló felderít® csapatok alkalmazása helyett szenzorhálózatokkal lenne a károk felmérése elvégezhet®.

2.3.2. Természetben történ® felhasználás A szenzorhálózatok környezeti alkalmazásai alatt érthetjük például a madarak vándorlásának követését, kisállatok ill. rovarok mozgásának monitorozását, környezeti folyamatok gyelését, melyek befolyásolják a termények és a haszonállatok fejl®dését. Szabályozhatjuk használatukkal például az öntözést, méréseket végezhetünk a föld alatt és a leveg®ben is, lehet®ség nyílik egyszóval a környezet monitorozására. A következ®kben néhány konkrét felhasználási lehet®ség vázolok fel.

Erd®tüzek detektálása A megfelel®en s¶r¶n telepített szenzorhálózatok lehet®séget biztosíthatnak erd®tüzek gyors észlelésére és a t¶zfészkek helyének pontos meghatározására, ezzel el®segítve a beavatkozást, miel®tt a t¶z még kontrollálhatatlanná válna. Technikai akadályok nem állják útját az akár több millió szenzorból álló hálózatok kiépítésének (ill. kiépülésének) sem. Ezeknek a szenzoroknak azonban nagy szükségük van arra, hogy a környezetb®l tudjanak energiát nyerni, mivel itt a hálózat élettartamaként évtizedes intervallumokat szeretnénk megjelölni. Fontossá válik tehát a szenzorok ellátása pl. napelemekkel. A rádiófrekvenciás kommunikáció jó eszköz az esetlegesen mostoha környezeti viszonyok, mint például az er®sen tagozott talaj vagy a nagyon s¶r¶ erd® által okozott kommunikációs problémák áthidalására.

Biocomplexity mapping Ez az angol kifejezés napjainkig a m¶holdak által vagy repül®gépekr®l készített fényképek segítségével történ® környezetfeltárásra utalt. Ez azonban inkább csak a nagy volumen¶ jellegzetességek vizsgálatára alkalmas, mint például egyes állatfajok elterjedtségének vizsgálata. A szenzorhálózatok fogalmának megjelenésével lehet®ség nyílik sokkal aprólékosabb meggyelések elvégzésére is ezen a téren.

Árvízészlelés Az árvízek észlelése azon területek egyike, ahol már a gyakorlatban alkalmaznak szenzorhálózatokat. Az egyik ilyen rendszer az Egyesült Államokban m¶köd® ALERT. Ebben többféle szenzort alkalmaznak egyrészt es®érzékelésre, másrészt a vízszint és az id®járás gyelésére, melyek egy el®re megtervezett útvonalon juttatják el


21

mérési eredményeiket a központi állomáshoz, ahol a monitorozás és az adatbázisba mentés zajlik.

Mez®gazdasági precizitás növelése Szenzorhálózatok segítségével lehet®ség nyílik az ivóvízben lév® növényvéd®szer-mennyiség, a talajerózió ill. a légszennyezettség mérésére valós id®ben.

2.3.3. Egészségügyi alkalmazások Véleményem szerint ez a terület tekinthet® a legfontosabbnak a szenzorhálózatok alkalmazási lehet®ségei közül, els®sorban azért, mert az apró szenzorok segítségével eddig soha nem látott folyamatokba nyerhetünk betekintést az emberi testen belül. Számos alkalmazási lehet®ség ismert már, többek között a továbbfejlesztett diagnosztika, a páciensek alaposabb meggyelésének lehet®sége, a pontosított gyógyszer-adminisztráció vagy az orvosok és betegek mozgásának követése a kórházakon belül, ami vészhelyzetben életment® lehet. Néhány felhasználási példát az alábbiakban b®vebben is részletezek.

Fiziológiai monitorozás A páciensek ziológiai állapota valós id®ben követhet®vé válik, ami megkönnyíti az orvosnak a diagnózis felállítását. Ezek az adatok hosszútávon is tárolhatóak, ami komplex kórkép kialakítását teszi lehet®vé. Ugyanakkor a jelenleginél alaposabb meggyelés végezhet® szenzorok segítségével, akár még a beteg megbotlását is regisztrálhatjuk (ami utalhat például pillanatnyi egyensúlyvesztésre). A mai hosszútávú monitorozó eszközök nagy hibája, hogy nagy méretük mellett különleges bánásmódot is igényelnek, pl. a páciens nem fürödhet, amíg az eszközt viseli. Ez a negatívum kompenzálható szenzorhálózatok alkalmazásával, vagyis magasabb életmin®ség garantálható a súlyos betegek számára is.

Páciensek és orvosok követése a kórházon belül A páciensek mozgásszabadsága megnövelhet®, ha egy kis szenzort rögzítünk a testükhöz, ami által folyamatosan tudni lehet, hol járnak. Az orvosok szintén viselhetnének hasonló szenzorokat, ezáltal egy-egy nagyobb kórházon belül szükséghelyzetben mindig a legközelebb lév® orvost lehetne riasztani. Az így megspórolt id® életet menthet.

Gyógyszer-adminisztráció Ha mind a betegek, mind a gyógyszerek elláthatóak lennének szenzorokkal, akkor minimálisra csökkenne annak az esélye, hogy egy páciens nem


22

megfelel® orvosságot kap. Hiszen a betegen lév® szenzor ismerné visel®je betegségét és azonosítani tudná a számításba jöv® gyógyszereket az azokon lév® szenzorok segítségével.

Szervezeten belüli folyamatok vizsgálata A soha nem látott kicsiny méretekb®l adódóan tetsz®leges szervezeten belüli folyamatot lehetne szenzorok ill. szenzorhálózatok segítségével vizsgálni. A beteg egyszer¶en lenyelné a szenzort vagy beinjekcióznák azt a véráramába, esetleg minimális bemetszéssel beültetnék azt a vizsgálandó testtájékra. Ezek után a szenzor képes lenne pontos adatokat sugározni a területr®l, ahol épp a testen belül tartozkodik. Tudomásom szerint a jelenlegi legfejlettebb ilyen eszköz - ami a mi szóhasználatunkban még nem min®sül szenzornak - egy pirulányi méret¶ mikrokamera, amely a bélrendszeren képes végighaladni és közben pillanatfelvételeket készíteni. Érezhet®, hogy itt még van hova fejl®dni!

2.3.4. Otthoni alkalmazások A szenzorhálózatok otthoni alkalmazása a jobb életkörülmények elérését célozza. Számos egyszer¶ alkalmazás már ma is elérhet®, amiket még érzékel®kkel valósítottak meg, viszont a szenzorok elterjedésével ezen alkalmazások száma és min®ségi jelent®s mértékben n®ni fog.

Lakás-automatizálás A technológia fejl®désével a különböz® háztartási eszközök elláthatóvá válnak szenzorokkal, amelyek mind egymással, mind a külvilággal kommunikálni tudnak - utóbbira például Internet-kapcsolat segítségével nyílik lehet®ségük. Így a tulajdonos távolról is irányíthatja háztartási eszközeit, de a helyi irányítás irányítás is egyszer¶bbé válhat.

Intelligens otthon A bútorokba és a használati tárgyakba szenzorokat lehet integrálni, amelyek képesek egymással és a szobában lév® szerverrel kommunikálni. A szerverek egymással is kommunikálhatnak, feltérkepezhetik a lakást. A szenzorokba épített intelligencia képessé teszi azokat olyan összetett feladatok megoldására, mint például a tulajdonos napirendjének megtanulása el®zetes beprogramozás nélkül és az ehhez kapcsolódó adaptivitás. Az intelligens otthonokban alkalmazásra kerül® szenzorhálózatoknak megbízhatónak, perzisztensnek és a felhasználó számára láthatatlannak kell lenniük.


23

2.3.5. Egyéb kereskedelmi felhasználások Ez az utolsó kategória foglalja össze azokat a szenzorhálózati felhasználási formákat, amelyek az el®z® kategóriákba nem fértek bele. A kategorizálás tökéletlenségére utal, hogy számos ilyen létezik, többek között az anyagok fáradásának monitorozása, a termékek min®ségének ellen®rzése, az automatikus gyártósorok vezérlése, az interaktív játékok és az interaktív múzeumok, a lopásérzékelés, stb. Az alábbiakban ezek közül is bemutatok néhányat b®vebben.

Irodaépületek környezeti vezérlése A légkondícionálás és a f¶tés a legtöbb épületben központilag van vezérlve. El®fordulhat, hogy egy terem két végében néhány fok eltérés érzékelhet®, mert például a teremben csak egy h®érzékel® van és az szabályozza az összes klímaberendezést. Egy olcsó szenzorokból felépített szenzorhálózat is elég lenne ahhoz, hogy a szoba különböz® részein garantálja az azonos h®fokot egyszer¶en azáltal, hogy más-más szenzorok vezérelnék a különböz® klímaberendezéseket. Egy felmérés szerint az ilyen célú elosztott szenzorhálózatok alkalmazása évi 55 milliárd dollár megtakarítást jelentene az Egyesült Államokban.

Interaktív múzeumok A közeljöv®ben a gyerekek már interakcióba léphetnek majd a múzeumi tárgyakkal, annak érdekében, hogy többet tudjanak azokról tanulni. Ezek a tárgyak képesek lesznek valamilyen formában válaszolni az érintésre és a beszédre. Hasonlóképpen lehet®vé válik valós idej¶ ok-okozat játékok játszása, ami hatalmas segítség lehet a tudományok elsajátításában és a természetr®l tanulásban. Az egyik San Francisco-i múzeum - az Exploratorium - már rendelkezik néhánnyal a felsorolt képességek közül.

Gépjárm¶vek lopásvédelme A szenzorokat gépjárm¶vekbe integrálva azok képesek lehetnek a lopások észlelésére és kapcsolatba léphetnek az autó tulajdonosával például az interneten keresztül. Beavatkozó rendszerekkel kiegészítve a lopások meggátolhatóak lennének, a már ellopott gépkocsikat a tulajdonos korlátozott mértékben távvezérelhetné (pl. megsz¶ntethetné a motor üzemanyag-ellátását vagy bekapcsolhatná a vészvillogót és aktivizálhatná a riasztó hangszóróját).

Gépjárm¶vek követése Némileg a lopásvédelemhez tartozhat a gépjárm¶vek követésének kérdésköre is. Nagyvállalatok láthatják el autóikat szenzorokkal annak érdekében, hogy mindig tudják, hol tartózkodik az illet® járm¶ ill. hogy a legközelebbi


24

járm¶vet lehessen kirendelni egy-egy sürg®s esetben. Két megközelítése lehetséges a gépjárm¶követ® rendszer m¶ködésének: az els® megközelítésnél a járm¶ helyzetét a rá telepített szenzor határozza meg és ezt az adatot továbbítja a bázis felé. A másik megközelítésnél a szenzorok nem képesek egzakt helymeghatározásra, a járm¶ pozícióját a bázis határozza meg a szenzorok által küldött, egymástól mért távolságukat tartalmazó adatokból.

2.4. Szenzorhálózatok tervezési szempontjai Az alábbiakban részletezend® faktorok mind befolyással vannak a szenzorhálózatok tervezésére, mindazonáltal kevés olyan cikkel találkoztam, amelyik az összes itt összegy¶jtött kritériumot gyelembe vette volna. Pedig ezek ismerete nélkülözhetetlen a megfelel® tervezéshez és segíthet megítélni a szoftver- ill. hardvereszközök min®ségét [2].

Hibat¶rés A megbízhatóság, vagy más néven hibat¶rés a szenzorhálózat azon tulajdonsága, hogy képes néhány szenzor funkcióvesztését túlélni. Ez a funkcióvesztés adódhat az akkumulátor lemerüléséb®l, a szenzor megsemmisüléséb®l vagy például kommunikációs távolságon kívülre kerüléséb®l (ez az jelenti, hogy a szenzor már nem képes egyetlen szenzorral sem kommunikálni, mert azok olyan messze vannak t®le, hogy a legnagyobb energiájú adás sem éri el azokat). Néhány szenzor elvesztésének tehát nem szabad befolyásolnia a szenzorhálózat által végzett feladat sikeres teljesítését. A hibat¶rést Poisson-eloszlással modellezhetjük. Ha Rk (t) a k . szenzor megbízhatósága, akkor Rk (t) = e−λk t jelenti annak valószín¶ségét, hogy nem hibásodik meg a szenzor a (0, t) intervallumban. λk a k . szenzor meghibásodási valószín¶ségét jelöli. Megjegyzend®, hogy egy szenzorhálózat megbízhatósági szintjét érdemes annak várható környezetéhez és feladatához igazítani. Egy épületben elhelyezett hálózatnak fölösleges túlzottan nagy megbízhatóságúnak lennie, mert ott a szenzorok zikai sérülésének veszélye csekély és akár még az akkumulátorok újratöltése is megoldható. Teljesen más azonban a helyzet a katonai felhasználásnál, ahol a szenzorok komoly zikai ráhatásnak lehetnek kitéve és méréseik emberéleteket menthetnek. Ilyenkor törekedni kell az átlagos felüli hibat¶résre.

Skálázhatóság A szenzors¶r¶ség egy meggyelend® területen több nagyságrendnyi átfogással is rendelkezhet. Elképzelhet® például mindössze 15-20 csomópont alkalma-


25

zása az adott területen, de ugyanúgy telepíthetünk akár egymillió szenzort is egy jól körülhatárolható részre. A jöv®ben fejlesztend® alkalmazásoknak és hardvereknek számolniuk kell a szenzorhálózatok természetéb®l adódó s¶r¶ elhelyezkedéssel. A szenzors¶r¶séget a következ® képlettel számohatjuk: µ(R) = (N πR2 )/A, ahol N az A területen lehelyezett szenzorok száma, R a rádiós kommunikáció maximális távolsága. Manapság a szenzors¶r¶ség még kicsinek tekinthet®, viszont robbanásszer¶ növekedése prognosztizálható. Természetesen ez az érték függ a szenzorhálózat alkalmazási területét®l is: munkafolyamatok felügyeletére vagy min®ségellen®rzésre sokkal több szenzor szükséges, mint az autók nyomonkövetésére, hiszen utóbbi esetben a legnagyobb s¶r¶séget feltételezve sincs 10-15 szenzornál több egy 25 m2 -es területen. Jelenleg az átlagos szenzors¶r¶ség 20 szenzor/m3 -re tehet®. A közeljöv®ben ez a szám drasztikusan meg fog n®ni. Képzeljük csak el azt az esetet, amikor már minden használati tárgyunk tartalmaz valamilyen szenzort és elmegyünk egy tömött stadionba megnézni egy focimeccset!

El®állítási költség Mivel a szenzorhálózatok sok szenzorból állnak, nagyon fontos, hogy egy szenzor el®állítási költsége alacsony legyen, különben a nagyobb hálózatok nem lennének megzethet®ek. Jelenleg a Bleutooth rádiós rendszerek ára 10$ körül mozog, míg az ún. PicoNode-oké 1$-ra tehet® [1]. A szenzorhálózatok széleskör¶ elterjedésének feltétele, hogy a szenzorok ára 1 cent alá essen! Látható, hogy ez egy nagyon komoly kritérium és egyben koniktusban áll az összes többi tervezési megfontolással.

Hardverszükségletek Számos pontban kell megfelelnie egy szenzornak a t®le elvárt teljesítménynek. Ez csak megfelel®, jó min®ség¶ hardver felhasználása esetén lehetséges, csak így lesz képes a szenzor - akár a többi szenzorral együttm¶ködve - végrehajtani a megjelölt mérési feladatot. A szenzorok zikai felépítésér®l már volt szó a 2.1. fejezetben, ezért itt most csak néhány konkrét elvárást említenék meg. A szenzoroknak amellett, hogy nagyon alacsony energiafogyasztás mellett kell képesnek lenniük a m¶ködésre, meg kell bírkozniuk a nagy szenzors¶r¶séggel is (ami interferenciához és bonyolult routing algoritmusok alkalmazásához vezethet). Alacsony el®állítási költségük ellenére autonóm módon kell tudniuk m¶ködni és adaptívnak kell lenniük a környezeti változásokkal szemben. Ezen kritériumok felsorolása után már talán érthet®, miért nagy kihívás az, hogy a szenzorok mérete 1 mm3 alá süllyedjen és súlyuk is mindössze 1 g töredéke legyen.


26

Hálózati topológia A szenzorhálózatok topológiája er®sen változónak tekinthet®, gondoljunk csak a mozgó szenzorokra ill. a lemerül® akkumulátorokra. Három kategóriába csoportosíthatjuk a topológiai változásokat:

Telepítés A hálózat kezdeti topológiáját annak els® telepítése, vagyis a szenzorok els® lehelyezése adja. Ez történhet például úgy, hogy repül®gépb®l kidobják a szenzorokat, valamilyen hordozórakétával átlövik azokat a megfelel® területre vagy akár valaki egyenként is lehelyezheti ®ket. Fontos szempont lehet az el®zetes topológiatervezés szükségtelenségének biztosítása.

M¶ködés A hálózat m¶ködése közben a szenzorok mozoghatnak, akkumulátoruk lemerülésével használhatatlanná válhatnak, megsemmisülhetnek, stb. Törekedni kell a tervezés során arra, hogy a m¶ködés közbeni topológiaváltozást is gyelembe véve minimalizáljuk a hálózat költségeit és biztosítsuk annak exibilitását.

Újratelepítés A hálózatnak m¶ködés közben is b®víthet®nek kell lennie, akár új területek monitorozásával kapcsolatban, akár a használhatatlanná vált szenzorok cseréjét tekintve. Mindkét eset bekövetkezése a hálózat újraszervezését igényli.

Környezet Többször is tettem már említést a szenzorok alkalmazási környezeteir®l, itt azonban újra meg kell ezt említeni. Megpróbálom néhány példával érzékeltetni, hogy milyen széls®séges viszonyokat kell egy csomópontnak adott esetben kibírnia lehet®leg tökéletes funkcionalitás mellett. Extrém magas h®mérsékleti viszonyokkal kerül szembe a szenzor pl. biológiai- és vegyi támadások észlelésénél. Pont ennek ellenkez®jére kell számítani a sarkvidéki alkalmazásoknál. Magas nyomású környezeti példaként említhetjük az óceán alján végzett méréseket, míg kivételesen zajos környezetre a szándékos zavarás vagy a túl s¶r¶ lehelyezés lehet jó példa. Látható, hogy minden zikai jellemz®re külön-külön is igaz a több nagyságrendnyi átfogás, mégis mindegyik fajta szenzornak olcsónak és kicsinek kell lennie!

Átviteli médium A többugrásos vezetéknélküli hálózatok vagy rádióhullám segítségével, vagy optikai eszközökkel kommunikálnak. Az optikai eszközök csak akkor használhatóak, ha a kommunikáló felek láthatósága garantálható, ami általában nem jellemz® a szenzorhálózatokra. Így ott inkább a rádióhullámmal történ® adatcserét preferáljuk. Manapság a szenzorhálózatok a licenszmentes szabad sávokat használják, azok


27

közül is a magasabb frekvenciatartományokat (ennek energiafelhasználási és hatékonysági okai vannak, ami els®sorban az antenna-karakterisztikákkal függ össze). A szabad frekvenciasávok használatának oka az, hogy ingyenes, széles spektrummal rendelkezik és bárhol elérhet®. Fontos megjegyezni azonban, hogy például a vízben történ® alkalmazásoknál újfajta jeltovábbítási formára lehet szükség, míg a csatatereken például számolni kell a nagymérték¶ csatornahiba-aránnyal. A szenzorok általában nem rendelkeznek a jelenleg használatos rádiós eszközök er®forrásaival, így a megfelel® átviteli médium kiválasztása továbbra is feladat.

Energiafogyasztás Egy csomópont már a méretéb®l kifolyólag is csak kicsiny akkumulátorral rendelkezhet (< 0.5 Ah, 1.2 V ), aminek az újratöltése vagy cseréje gyakran nem kivitelezhet®. Így a szenzorok élettartamának els®számú indikátorává válik az akkumulátor töltöttsége. Három folyamat energiafogyasztása adja a szenzor által elhasznált töltésmennyiséget: az érzékelés, a kommunikáció és az adatfeldolgozás. Az érzékelés során fontos, hogy egyfolytában mérünk, vagy csak id®közönként, meghatározó az alkalmazási rétegbeli protokollok hatékonysága illetve a mérend® jelenség vagy mennyiség természete is. A kommunikáció a legjelent®sebb tényez® a felsorolt három közül. A 2.2.4. alfejezetben már volt róla szó, hogy nem érdemes a szenzorok rádió adó-vev®jét kis csomagméretek mellett ki- és bekapcsolgatni, hiszen akkor az áramkörök a néhány száz mikroszekundumos feléledési id® alatt is annyi áramot fogyasztanak, hogy már az kezd el dominálni, nem pedig a hasznos (csomagok küldésére fordított) energiafogyasztás. Sajnos a kommunikáció a zikai törvények miatt már eleve nagyon költséges (lsd. 2.2.5. alfejezet), komoly er®feszítéseket kell tehát tennünk az energiafogyasztás minimalizálása érdekében. Az adatfeldolgozás kritikusságára talán az az összefüggés világít rá legjobban, amely szerint az α = 4 esetben 1 KB adat 100 m-re történ® továbbítása megközelít®leg ugyanannyi energiát igényel, mint 3 millió utasítás végrehajtása egy 100 millió utasítás/másodperc sebesség¶ processzoron. Érdemes tehát a kapott adatokat feldolgozni és csak a feldolgozott (ezáltal méretükben kisebb) állományokat továbbküldeni. A szenzorokat érdemes lehet tehát ennek érdekében adatfeldolgozó szoftverekkel felszerelni.

3. fejezet Csomagtovábbítás szenzorhálózatokban Az el®z® fejezetben áttekintettük a szenzorok felépítését, a szenzorhálózatok felhasználási lehet®ségeit és rendszereztük azokat a tényez®ket, amelyekre gyelemmel kell lenni szenzorok és szenzorhálózatok tervezése során. Ebben a fejezetben már a konkrétan számunkra érdekes témaköröket részletezem. Az els® ilyen a routing, vagyis az útválasztás. Az útválasztás során d®l el, hogy a szenzorok mely másik szenzorokat tekintik szomszéduknak, amelyekkel kés®bb kommunikálni is fognak. Ez a témakör ugyan nem szerves része a spontán kooperáció kérdéskörének, viszont a teljesség igényét szem el®tt tartva mindenképpen említést kell tenni róla. A fejezet második harmadában a szenzorok rosszindulatú viselkedésér®l és a serkentés hatására kialakuló kooperációról lesz szó. Végül bevezetem a spontán kooperáció fogalmát és áttekintést adok a kapcsolódó irodalmakról.

3.1. Útválasztás Az útválasztás megértéséhez el®ször a címzési eljárásokkal kell megismerkedni. Címzés alatt azt értjük, hogy milyen módon tud a bázis egy kiválasztott csomópontot megszólítani. A tradícionális hálózatokban, pl. az Interneten a címzés x címek segítségével történik (IP cím). Ezen megoldás el®nye, hogy a címek egyediek lehetnek. Sajnos az egyedi címek karbantartása nagyon komoly szervezést igényl®, drága megoldás. Ez a probléma a mobil hálózatok kapcsán mérgesedett el, ahol a topológiai információk folyamatosan változnak. Rendkívül nehéz a csomagokat úgy irányítani, ha a címzett címe nem szolgál támpontként a csomag továbbításának megfelel® irányára vonatkozóan. A szenzorhálózatokban mindazonáltal maga az információfolyam természete volt segítsé28

3. FEJEZET. CSOMAGTOVÁBBÍTÁS SZENZORHÁLÓZATOKBAN

29

günkre a címzési probléma megoldásában. A legtöbb lekérdezés ugyanis a következ® formában érkezik: Kérem a 3. emeleti szenzorok méréseit!. Így a csomópontok a saját pozíciójuk alapján címezhet®k (ami nem jelenti a helymeghatározó rendszer integrálásának szükségességet, csak felületes információ birtoklását a konkrét pozícióról), ez pedig megteremti a kívánt segítséget az útválasztó prokollok számára. Ezt a megoldást osztályalapú

címzésnek nevezzük, mivel a szenzoroknak egy halmazát, másnéven osztályát szólítja meg a protokoll. Másik lehet®ség az attribútum-alapú címzés, ahol szintén egy, a szenzorhálózatokban áramló információ típusára vonatkozó jellemz®t ragadunk meg. Konkrétan arra utalok, hogy szintén gyakori lekérdezés a következ®: Azon szenzorok jelentkezzenek, amelyeknél a mért h®mérséklet meghaladja a 25 ◦ C -ot!. Itt tehát a mérend® jelenség attribútumát hívjuk segítségül a szenzorok eléréséhez. Ez nyilván egy egészen más megközelítés, mint az el®z®, annak ellenére, hogy ugyanúgy szenzorok egy csoportját címezi meg. A legegyszer¶bb bár a megvalósítás és a használat szempontjából a legnagyobb odagyelést igényl® megoldás az, ha feltételezzük, hogy a bázisállomás mindig naprakészen ismeri a szenzorok pozícióját. Ez ugyan ellentmond a napjainkban jellemz® elosztott rendszer-szemléletnek, viszont amíg a szenzorhálózatok, mint kutatási téma olyan kiforratlan, mint manapság, addig jó közelítésnek tekinthet® és segít abban, hogy a kutatók más problémákra is összpontosíthassanak ebben a témakörben. Másik el®nye, hogy ezzel a módszerrel a szenzorok külön-külön is elérhet®vé válnak.

3.1.1. Útválasztási algoritmusok A szenzorhálózatokkal kapcsolatos kutatások megkezd®dése óta számos routing protokollt javasoltak már, melyek gyelembe vették a vezetéknélküli közeg hátrányait, többek között az alacsony sávszélességet, a magas csatornahiba-arányt, ill. a mobil ad hoc hálózatokra jellemz® gyakori topológiaváltozást és az alacsony akkumulátor-kapacitást. A protokolloknak ezeken kívül még a nagy szenzorszámmal is meg kell bírkózniuk. A megoldásokat alapvet®en két kategóriába sorolhatjuk, beszélhetünk proaktív és reaktív protokollokról.

Proaktív protokollok A proaktív protokollok jellegzetessége, hogy minden csomópont mindig aktuális információval rendelkezik arról, hogy milyen utakon lehet a hálózat bármely más szenzorát elérni.


30

Minden szenzor karbantart egy vagy több routing táblát, amelyekben az útválasztási információkat tárolja, a topológiaváltozásokat pedig minden csomópont továbbítja, így a szenzorok tudása kis késleltetéssel mindig az aktuális állapotot fogja tükrözni. A protokollok között különbség lehet a routing táblák számában és a topológia-változási információk terjesztésének módjában. Két tipikus proaktívt protokollt mutatok be röviden példaként.

• Destination-Sequenced Distance-Vector Routing A DSDV protokoll [9] a BellmanFord algoritmus alapján m¶ködik, vagyis minden csomóponthoz, mint forráshoz megkeresi az összes többi csomóponthoz vezet® legkisebb súlyú utat és biztosítja, hogy ne legyen kör a routing gráfban. Minden csomópont számon tartja tehát a következ® ugrást (a szomszédját egy bizonyos úton) és a távolság-információkat minden más csomópontra vonatkozóan. A topológia-változásról a csomópontok periódikusan kapnak értesítést.

• Link-State Routing Ez szintén egy proaktív útválasztási megoldás, melyben minden csomópont közzéteszi, hogy milyen költséggel tud kommunikálna a különböz® linkeken. Ezek alapján minden csomópont ki tud számolni egy legrövidebb utat minden másik csomóponthoz. A link-state útválasztó algoritmus [10] egyirányú linkek esetén is jól m¶ködik, míg az el®z® megoldás csak kétirányúakra alkalmazható.

Reaktív protokollok A proaktív prokollokkal ellentétben a reaktív protokollok csak akkor építenek fel egy utat, ha arra szükség is van. Ez azt jelenti, hogy egy explicit útfeltáró alkalmazással rendelkeznek a szenzorok, amely csak igény felmerülése esetén lép m¶ködésbe. Ez az útfeltárás lehet a forrás vagy a vev® által kezdeményezett. El®bbi azt jelenti, hogy az adatforrás kezdeményezi az útfeltárást a vev® felé, utóbbi ennek az ellenkez®je. Egy út kiépülése után az útfeltáró algoritmus befejezi m¶ködését és egy karbantartó procedúra addig kezeli a kialakított utat, amíg az végleg össze nem omlik vagy már nincs szükség rá. Itt is megemlítek néhány példát.

• Ad Hoc On-Demand Distance Vector Routing Az AODV protokoll [11] a DSDVhez hasonlóan távolságvektor alapú, de ez nem proaktív, hanem reaktív. A forrás inicializálja az út kiépítését, amikor észreveszi, hogy csomagot kellene küldenie, de nincs meg az ahhoz szükséges út. A forrás szétküld egy kérvényt (request), amely


31

addig utazik a hálózaton, míg el nem ér a címzetthez vagy útközben rá nem talál egy elég friss útra. A kérvény érkezésekor minden csomópont megjegyzi, hogy kit®l kapta azt meg el®ször, így a visszafelé vezet® út ismertté válik.

• Dynamic Source Routing A DSR [12] szintén egy forrás által inicializált, reaktív protokoll, ami a forrás általi útválasztáson alapul. Ez azt jelenti, hogy a forrás határozza meg a teljes utat, amit a csomagnak be kell járnia, nem csak a következ® ugrást. Ha a forrás nem ismeri a teljes utat, akkor kérvényekkel árasztja el a hálózatot, amire bárki válaszolhat, akinek van teljes útja a célig - ekkor a már meglév® út információit is el kell küldeni a forrásnak. Ezután az egész út bekerül a forrás által küldött csomag fejlécébe, innen tudják meg a közbens® állomások, kinek kell továbbítaniuk az üzenetet.

• Directed Diusion Ez egy mer®ben más kommunikációs paradigma, kifejezetten szenzorhálózatok számára kifejlesztve. A Directed Diusion [13] adatközpontú és alkalmazásfügg®, osztályalapú címzéssel m¶köd® routing technika. Itt a vev® kezdeményezi az adatáramlást egy lekérdezéssel árasztva el a hálózatot, mellyel kapcsolatban minden csomópont feljegyzi, hogy kit®l is kapta, majd továbbadja azt. Végül a lekérdezés elér a címzett szenzorhoz és kiépül a visszafelé irányuló út, amelyiken minden továbbító csak az úton szomszédos szenzort ismeri, az adat végs® felhasználóját nem. Miután várhatóan több út is kiépül párhuzamos ezzel az eljárással (hiszen az elárasztással küldött lekérdezést mindenki megkapja és mindenki tovább is adja), szükség van egy pozitív meger®sítésre a használni kívánt úttal kapcsolatban. A következ®kben bemutatok néhány egyszer¶, ugyanakkor hatékony útválasztási eljárást, amelyek az irodalomban fellelhet®ek [2]. A 3.1. ábrát tekintve több egyszer¶ útválasztási megoldás is eszünkbe juthat. Az ábrán felül látható a bázis, ahova a csomag küld®je (forrás) szeretne egy üzenetet eljuttatni. A szenzorok mellett azok megnevezése (A, B, stb.) és energiatartalékuk szerepel zárójelben. A linkek mellett azok használatának költsége látható. Az említett egyszer¶ megoldások például a következ®k lehetnek.

• A maximális energiatartalékú út választása azt jelenti, hogy azon az úton küldjük a csomagunkat, amelyiken a szenzorok összes energiatartaléka a legnagyobb. A példánkon ez a forrás-C-B-A-bázis út lenne. Sajnos ez az eljárás nem hatékony, hiszen látható is, hogy a C pont fölösleges az útban, s®t rossz, hogy ott van.


32

bázis

2

1 2

E (1)

A (2) D (3)

1

2 B (2)

2 F (4)

2 2 C(2)

2

forrás

3.1. ábra. Útválasztási példa

• A minimális energiájú út algoritmus a linkhasználat költségösszegének minimumára törekszik. Egyszer¶en az el®bbi algoritmushoz hasonlóan az összes lehetséges utat megvizsgálva kiválasztja azt, amelyiken a legkisebb energia felhasználásával lehet eljutni a forrástól a bázisig. Jelen esetben ez a forrás-B-A-bázis út.

• Minimális ugrásszámú útról beszélünk, ha a továbbításban résztvev® csomópontok számát akarjuk minimalizálni. Az ábránkon ez a forrás-D-bázis útvonal, amely csak egyetlen ugrást tartalmaz. Itt is felmerül a probléma, hogy ez az út láthatóan nem hatékony. Az algoritmusunk akkor lenne használható, ha a linkek használatának költsége mindenhol megegyezne, ekkor lényegében újra eljutnánk a minimális energiájú út algoritmusához. Elképzelhet®ek ennél jóval bonyolultabb algoritmusok is. Kiemelném a [7]-ban található Energy Aware Routing nev¶ megoldást. Ott a szerz®k arra hívják fel a gyelmet, hogy a kevésbé mobilis hálózatok esetében a statikus utak használata bármilyen algoritmussal is állítják azt el® néhány központi helyen lév® továbbító szenzor gyors lemerülését eredményezheti. A megoldás a cikk szerint a valószín¶ségi alapra helyezett útválasztásban rejlik, vagyis minden csomópontnak több utat is ismernie kell a bázis felé és ugyan nagy valószín¶séggel úgyis a legkevesebb energiát igényl®t használja, id®nként mégis el


33

kell térnie attól egy másik szuboptimális megoldás felé, hogy kímélje a minimális energiát igényl® úton a szenzorok akkumulátorát, ezzel mintegy meghosszabbítva az út élettartamát. A cikk akár 40%-os javulásról is beszámol a hálózat élettartama szempontjából az ismert routing sémákhoz képest, mint amilyen pédául a Directed Diusion. További el®nyként jelentkezik a hálózat topológiailag egyenletesebb energiafelhasználása és a hirtelen szolgáltatás-megsz¶nés kiküszöbölése, az ún. graceful degradation. Sajnálatos módon utóbbi algoritmus implementálása után szembesültem annak lassúságával, ami olyan mérték¶ volt, hogy a szimulációs esetek lefuttatásának id®tartama megengedhetetlenül hosszúra nyúlt volna. Ez véleményem szerint egyben azt is jelenti, hogy ezen algoritmus használhatósága a szenzorhálózatok körében megkérd®jelezhet®, hiszen ezek az er®forrásaik sz¶kösségével jellemezhet® rendszerek aligha fognak tudni ilyen bonyolult algoritmusokkal hatékonyan megbírkózni. El®z®ekb®l tanulva végülis a már említett minimális energiájú út (Minimum Energy Path) algoritmusának használata mellett döntöttem. Az általam írt, szenzorhálózatokat szimuláló programban (lsd. 6. fejezet) az algoritmus a következ® módon m¶ködik. A bázistól elindulva visszafelé építi ki az utat minden szenzor felé, el®ször megkeresve a bázishoz legközelebb es® szenzort. Annak elhelyezkedését és bázistól vett távolságát megjegyezve a még el nem rendezett szenzorok közül keresi meg a bázishoz legközelebb es®t, majd megvizsgálja, hogy annak a közvetlen kommunikáció vagy az el®bbi szenzoron, mint ugráson keresztüli adás az el®nyösebb-e (a kommunikáció költségével kapcsolatban lásd a 2.2.5. alfejezetet). Ezután már két szenzorunkhoz is meg van a legkisebb költség¶ út, az algoritmus pedig az el®z®ekhez hasonlóan halad tovább, míg az összes csomóponthoz nem rendel megfelel® utat. Az algoritmus m¶ködésének befejeztével minden csomópont tudni fogja, hogy melyik másik csomópontnak kell az üzenetet küldenie, amit a bázisnak szán (vagyis melyik számára a következ® ugrás), mennyi ennek a küldésnek a költsége és mennyi a minimális energiájú út során fellép® összköltség, ami a hálózatot terheli. Megjegyzend®, hogy minden szenzor két továbbító csomópontot jegyez: egyet a kooperatív lépéseknek és egy másikat a nem kooperatívaknak. Kooperatív lépések esetén mindkét szervezet szenzorai lehetnek továbbító csomópontok, vagyis az algoritmus az összes szenzort gyelembe véve fut le, míg nem kooperatív lépés esetén csak a saját hálózatbeli szenzorokat használjuk. Természetesen a két továbbító csomópont meg is egyezhet, ha a hálózat topológiája azt eredményezi.


34

Fontos látni, hogy a leírt algoritmus nem útválasztási protokoll. Vagyis a programban nem foglalkoztam az útválasztás folyamatának szimulációjával, hanem feltételeztem, hogy a szenzorok ismerik a bázis felé vezet® utakat. Ez az ismeret a fenti központosított algoritmus lefuttatásával válik elérhet®vé, ami még a hálózat m¶ködésének megkezdése el®tt kiszámítja a szenzorok számára a megfelel® utakat. Az algoritmus eredménye ideális esetben megegyezik az elosztott protokollfuttatás eredményével.

3.2. Kooperáció ösztönzéssel Az ad hoc hálózat m¶ködése és így az általa nyújtott szolgáltatások rendelkezésre állása is arra a feltevésre épül, hogy a hálózat résztvev®i kooperatívan viselkednek, azaz hajlandóak egymás számára szolgáltatásokat nyújtani. Ezt azonban semmi sem garantálja. Éppen ellenkez®leg: mivel a kooperatív viselkedés szolgáltatások nyújtását (pl. mások csomagjainak továbbítását) jelenti, ami viszont energiafogyasztással jár, a tipikusan telepr®l üzemel® résztvev®k telepük élettartamának növelése érdekében esetleg megtagadhatják az együttm¶ködést. Annál is inkább, mert a kooperatív viselkedés önmagában még nem garantálja egy adott résztvev® számára, hogy a többi résztvev® is kooperatívan fog viselkedni vele szemben. Valójában egy önz® résztvev® parazita módon kihasználhatja a hálózat kooperáló résztvev®it saját csomagjainak továbbítására anélkül, hogy ® maga egyetlen csomagot is továbbítana (vagy egyéb szolgáltatást nyújtana) mások számára. Ezért fontos valamilyen kooperációra ösztönz® mechanizmus bevezetése a hálózatba. Hasonló jelleg¶ probléma hagyományos hálózatokban lényegében nem létezik. A nemkooperatív viselkedésnek több fajtája is létezik, melyeket a 3.2. ábra szerint osztályozhatunk [15].

Indokolt nem kooperatív viselkedés Az er®források sz¶kösségéb®l adódó nem kooperatív viselkedés lehet átmeneti vagy állandó, attól függ®en, hogy az er®forráshiány átmeneti-e vagy állandó. Állandó hiány akkor lép fel, ha az eszköznek nem áll rendelkezésére az er®forrás, például ha nincs elég számítási kapacitása vagy memóriája. Átmeneti hiány akkor léphet fel, ha például hirtelen nagy forgalom zúdul az eszközre. Ezekben az esetekben az ösztönz® mechanizmusnak nem szabad büntetnie az eszközt. Ehhez fel kell ismerni az indokolt nem kooperatív viselkedést, és meg kell azt különböztetni az indokolatlan nem kooperatív viselkedést®l.


35

Nem kooperatív viselkedés

Indokolt nem kooperatív viselkedés

Csalás

Kifizetõdõ csalás

Önzõ viselkedés

Rosszindulatú viselkedés

Pazarló viselkedés

3.2. ábra. Nem kooperatív viselkedés osztályozása

Csalás Az indokolatlan nem kooperatív viselkedést nevezzük most csalásnak. Itt arról van szó, hogy az eszköz annak ellenére nem viselkedik kooperatív módon, hogy lehet®sége lenne arra. Ez akkor következik be, ha az eszköznek valamilyen módon haszna származik a kooperáció megtagadásából. Ezt a viselkedési formát büntetni kell.

Rosszindulatú viselkedés A rosszindulatú viselkedés egy nem gazdaságos viselkedési forma, ezért csak akkor fordulhat el®, ha egy magasabb rétegnek az el®nyös. Például egy hírnév alapú hálózatban rágalmazó üzeneteket küldeni nem kizet®d® a hálózati réteg számára, viszont jó lehet az alkalmazási réteg számára, ha ezzel egy vetélytársát ki tudja zárni a hálózatból.

Kizet®d® csalás Kizet®d® csalásról akkor beszélünk, ha az eszköznek direkt úton haszna származik a nem kooperatív viselkedéséb®l, vagyis pl. energiát képes spórolni. Két fajtája az önz®- és a pazarló viselkedésformák.

Pazarló viselkedés Pazarló viselkedés esetén az eszköz fölöslegesen használja fel a hálózat adta lehet®ségeket, pl. fölösleges adatfolyamokat küld. Ezzel terheli a hálózat többi résztvev®jét, vagyis rövidíti a hálózat élettartamát. El®fordulhat, hogy ez a viselkedés több szenzor számára is hasznos (pl. értékes információkat tud az adatfolyamból kinyerni), viszont soha sem elegend® mennyiség¶ szenzor számára, mert akkor kooperatív viselkedés lenne.

Önz® viselkedés Egy egy kizet®d® viselkedési forma, amikor is az eszköz csak a saját érdekeit tartja szem el®tt, pl. soha nem továbbítja a szomszédai csomagjait annak


36

ellenére, hogy az módjában állna.

3.2.1. Ösztönz® sémákkal szemben támasztott követelmények Ahhoz, hogy a kooperativitásra ösztönz® modellek sikerrel teljesítsék feladatukat, számos kritériumnak kell megfelelniük az alábbi területeken.

Hatékonyság Egy eektív ösztönz® mechanizmus visszaszorítja az együttm¶ködés megtagadását, kivéve természetesen az indokolt eseteket. Ez a megbízott fél kompenzálásával történik, ami mind az önz® m¶ködésre, mind a másik fél kihasználására megoldást jelenthet. A indokolt együttm¶ködés-megtagadás felismerésére aszimmetrikus kooperációs sémákat használnak. A nyilvános kulcsú titkosítás látszólag jó megoldást jelenthet az integritás, a hitelesség és a letagadhatatlanság kérdésére, viszont túlzott er®forrásigénye miatt általában nem hatékony.

Bizalom A használt modellt®l függ®en a bizalom lehet a kooperáció ösztönz®je vagy el®feltétele. A megbízónak bíznia kell a megbízottban, hogy az elvégzi a kapott feladatot és nem képes extra juttatásokat követelni. A megbízottnak pedig bíznia kell abban, hogy a kapott juttatásai érvényesek. Kétféle bizalmi séma terjedt el:

• Statikus bizalomról beszélünk, ha a bizalom mértéke az id®t®l független. Ez a megközelítés jellemz®en tanúsítványokat használ, melyek visszavonásukig érvényesek. A statikus bizalom tranzitív és általában nyilvános kulcsú titkosítással együtt implementálják, ami robosztussá teszi a rendszert, viszont nagy igényeket támaszt azzal szemben.

• A dinamikus bizalom az id®ben változik. Az A entitás B-re vonatkozó bizalma annak B-vel kapcsolatos tapasztalataiból, ill. a többi entitás B-vel kapcsolatos tapasztalataiból ered. Az entitások ezekb®l a tapasztalatokból a hírnév szétárasztásával (diusion of reputation) és lehallgatással (sning) tanulhatnak.

Tranzakció Az alapvet® megbízómegbízott kooperáció két részb®l áll: el®ször is megegyezés születik a megbízott honorálásánák mértékér®l és az általa elvégzend® feladatokról, majd a megbízott végrehajtja a feladatot és megkapja az azért járó térítést. A térítés mértéke általában függ a megbízó költség/haszon hányadosától. A feladat


37

elvégzésének és a térítés kizetésének együtt egyetlen atomi m¶veletnek kellene lennie. Mivel ez feltétlen kooperativitást kívánna, nem követelhet® meg. A rosszindulatú viselkedés (túlszámlázás, feladat végre nem hajtása, stb.) ellen védhet a térítés kisebb összegekben való, megoldott feladatrészekt®l függ® kizetése. Vagyis ekkor mind a feladatot, mind az azért járó zetséget kisebb részekre osztjuk, és felváltva történik a feladat végrehajtása és a zetés. A probléma itt az, hogy megnövekedett üzenetszám nagy overheadet jelenthet. Ebb®l a szempontból tehát inkább a tranzakciók összevonása t¶nik jó megoldásnak, ehhez viszont a megbízónak és a megbízottnak hosszútávú együttm¶ködésben kell megállapodnia.

3.2.2. Ösztönz® sémák díjazási típusai Az ösztönz® sémák legfontosabb eleme a díjazás. A megbízó zet a megbízottnak, hogy az számára valamilyen feladatot elvégezzen, pl. számításokat hajtson végre vagy csomagokat továbbítson. A díjazásnak két alapvet® típusa terjedt el széles körben: a hírnév alapú díjazás és a számla alapú díjazás. Hírnév alapú díjazás esetén a térítés mértéke függ az entitás hírnevét®l. Az A entitás szempontjából a B entitás hírneve A-nak B-vel kapcsolatos tapasztalataiból és a többi entitás B-vel kapcsolatos tapasztalataiból ered. Az A entitás B-vel kapcsolatos bizalmát pedig B hírneve határozza meg dinamikus bizalmi séma alkalmazásával. Egy entitás hírneve csak a vele korábban kapcsolatba került entitások által ismert, ill. a hírnév szétárasztása által a környez® entitások is ismerhetik. Ebb®l látható, hogy a jó hírnév csak stabil vagy lokalizált interakciós minták esetén kizet®d®. Hírnév alapú díjazási séma használata esetén a díjazásban való megegyezés fázisa kimarad, mivel a térítés mértékét a megbízó egyedül határozza meg. A hírnév valódi pénzzé konvertálása egyel®re nem megoldott, így ezen séma pénzügyi alkalmazása er®sen korlátozott. Hírnév alapú ösztönzési sémákra számos példa található az irodalomban (pl. [21, 22, 23]). Számla alapú díjazás esetén minden entitás rendelkezik egy számlával egy virtuális banknál. A megbízó minden tranzakciónál kibocsát egy csekket, mellyel a megbízott a virtuális bank közrem¶ködésével visszatérítést kap az elvégzett feladatokért. A bank elérhet®sége el®feltétele a módszer helyes m¶ködésének, ezért szokás azt több kisebb lokális bank csomópontra partícionálni. El®fordulhat, hogy az entitás maga tárolja a saját számláját. Ehhez olyan modulokat kell az entitásokba beépíteni, melyek minden szempontból


38

megbízhatóak. A számla alapú díjazás egy statikus bizalmi séma. Mivel minden entitás saját számlával rendelkezik, egyszer¶ a díjak valódi pénzzé átváltása. A probléma az lehet, hogy a számla alapú díjazás vagy megbízható hardverre, vagy a bank csomópontok elérhet®ségére épít, s ez ad hoc hálózatokban külön nehézségeket jelent. Számla alapú ösztönz® sémákra is számos példa található az irodalomban (pl. [16, 17, 18, 19]).

3.2.3. Példák számla alapú ösztönzési sémákra [17]-ben a szerz®k egy olyan módszert javasolnak a kooperatív viselkedés ösztönzésére, amely számla alapú díjazásra épül és nem használ virtuális bankot (azaz az eszközök tárolják a saját számlájukat). Ehhez természetesen biztosítani kell valamilyen zikai hozzáférésvédelmet, ami megakadályozza, hogy az eszköz gazdája hozzáférjen az eszközön tárolt számlához és manipulálni tudja azt. Egy lehetséges megoldás az lenne, ha az egész eszköz behatásálló hardverre épülne, ám ez nehezen kivitelezhet® és drága is. A javasolt megoldás csak annyit követel meg, hogy minden eszköz rendelkezzen egy behatásálló hardver modullal. Ez nem teljesíthetetlen követelmény, hiszen a mai mobil telefonokban is van ilyen modul, mégpedig a SIM kártya. A továbbiakban az eszközökben található behatásálló modult biztonsági modulnak nevezem. A biztonsági modulról tehát azt feltételezzük, hogy az abban futó programok m¶ködését az eszköz gazdája nem tudja módosítani, azaz azok helyesen, az el®írt protokollnak megfelel®en m¶ködnek. Ugyanakkor megengedjük, hogy az eszköz gazdája az eszköz biztonsági modulon kívüli részének m¶ködését tetsz®legesen módosítsa. A javasolt megoldás azonban biztosítja, hogy az eszköz gazdájának semmi haszna nem származik az eszköz m¶ködésének módosításából, ezért feltehet®en csak ritkán fog élni ezzel a lehet®séggel. Ezt a kritikus és nem kritikus funkciók körültekint® szétválasztásával és megfelel® kriptográai protokollok alkalmazásával érték el. A biztonsági modulra épül® ösztönz® séma m¶ködését a következ® módon foglalhatjuk össze röviden. Minden eszköznek van egy számlálója, melyet a biztonsági modul kezel, így ahhoz az eszköz gazdája nem fér hozzá. Ezt a számlálót nuglet-számlálónak nevezzük. Mikor az eszköz egy saját csomagot szeretne küldeni, akkor azt el®ször át kell adnia a biztonsági modulnak, ami egy kriptográailag védett fejlécet generál a csomag számára. Ezen kívül a biztonsági modulban fut az útválasztó algoritmus is, és így a modul meg tudja állapítani (vagy becsülni), hogy hány eszközön kell majd a csomagnak áthaladnia, amíg


39

megérkezik a címzetthez. Jelöljük a szükséges továbbító eszközök (becsült) számát n-nel. Miel®tt a biztonsági modul kiadná a csomag elküldéséhez szükséges biztonsági fejlécet, ellen®rzi, hogy a nuglet-számláló értéke nem kisebb-e, mint n. Ha igen, akkor a csomagot nem lehet elküldeni (nincs rá fedezet), és így a biztonsági modul nem adja ki a fejlécet az eszköz számára. Ha a nuglet-számláló értéke nagyobb, mint n, akkor a biztonsági modul

n-nel csökkenti azt, majd kiadja a fejlécet az eszköznek. Ezek után az eszköz elküldi a csomagot a biztonsági fejléccel együtt. Minden továbbító eszköz a biztonsági fejléccel együtt átadja a csomagot a saját biztonsági moduljának. A biztonsági modul csak akkor fogadja el a csomagot, ha a fejlécben található kriptográai ellen®rz®összeg helyes. Ekkor a biztonsági modul új fejlécet generál a csomaghoz, melyet majd a következ® továbbító eszköz biztonsági modulja fog ellen®rizni, és átadja az új fejlécet a továbbító eszköznek. Ezen kívül a biztonsági modul feljegyzi, hogy a megel®z® eszköznek (ha az nem maga a forrás volt) jár egy nuglet a csomag továbbításáért. Ezeket a feljegyzéseket minden szomszédra külön összegezve nyílvántartja a biztonsági modul, majd minden szomszéddal periódikusan futtat egy nuglet-szinkronizációs protokollt, melynek segítségével a két szomszéd kiegyenlíti tartozásait egymás felé. Egy továbbító eszköz csakis akkor kaphat zetséget a csomag továbbításáért, ha valóban továbbította azt, hiszen mindig a következ® eszköz biztonsági modulja jegyzi fel a továbbításért járó nugletet, ehhez azonban a csomagnak épségben meg kell érkeznie a következ® eszközhöz. Ha a csomag fejléce helytelen (vagy hiányzik), akkor a biztonsági modul nem fogadja el a csomagot, és így a továbbító eszköz nem kapja meg a továbbításért járó nugletet. Ezért egyetlen eszköznek sem áll érdekében fejléc nélküli vagy hibás fejléc¶ csomagot továbbítani. A csomag forrása tehát nem kerülheti el, hogy a csomagot elküldés el®tt átadja a biztonsági moduljának (hiszen csak az tudja a megfelel® fejlécet generálni) és ezzel együtt zessen a csomag elküldéséért. A fent leírt ösztönz® séma m¶ködését a szerz®k szimulációval elemezték. A szimulációban minden eszköz konstans átlagos sebességgel generált csomagokat véletlenszer¶en választott céleszközök számára. Ha egy eszköz egy saját csomagot a nuglet-számláló alacsony értéke miatt nem tudta a generálás után azonnal elküldeni, akkor eldobta azt (azaz nem használt puert a csomag ideiglenes tárolására). Minden eszköz célja az volt, hogy minimalizálja az eldobott csomagok számát. Több heurisztikus csomagtovábbítási stratégiát vizsgáltak a fenti feltevések mellett, és a szimulációk eredménye azt mutatta, hogy a kooperatívabb stratégiák általában jobb teljesítményt értek el (a fenti cél tekintetében),


40

mint a kevésbé kooperatívak. Más szavakkal, a javasolt eljárás valóban csomagtovábbításra ösztönözte az eszközöket, legalábbis a fenti feltevések mellett. A következ®kben egy másik példával is szemléltetni szeretném a számla alapú ösztönzési sémákat. Egy valószín¶ségi elv¶ mikrozetési módot fogok bemutatni, amelyet ugyan nem kimondottan szenzorhálózatok számára fejlesztettek ki (a megcélzott hálózattípus a többugrásos celluláris hálózat volt), viszont ennek ellenére nagy mértékben korrelál a szenzorhálózatok témaköréhez és rendkívül ötletes [18]. A probabilisztikus mikrozetés ötlete a következ®. Tegyük fel, hogy A szeretne B-nek zetni egy kis összeget, mondjuk 1 Forintot. A hagyományos mikrozetési sémákban A ezt úgy teszi meg, hogy átad B-nek egy 1 Forintot ér® elektronikus zsetont, amit B valódi pénzre vált be a virtuális bank segítségével. Ezzel szemben, probabilisztikus mikrozetés esetén A egy 1000 Forintot ér® elektronikus lottószelvényt ad át B-nek, amely azonban csak 1 1000

valószín¶séggel nyer. Az átadott szelvény várható monetáris értéke tehát pontosan 1

Forint. A probabilisztikus séma el®nye abból származik, hogy az átadott szelvény az esetek nagy többségében nem nyer, és így B nem fordul a virtuális bankhoz, hogy valódi pénzre váltsa az elektronikus szelvényt. Más szavakkal, a bank terheltsége nagy mértékben csökken. Ugyanakkor, ha B egy szolgáltató, aki sok felhasználóval bonyolít le a fentihez hasonló tranzakciót, akkor átlagosan ugyanannyit keres, mint a hagyományos zetési sémát használva (feltéve, hogy az egyes lottószelvények nyerései egymástól független események). Ha A is sok tranzakciót bonyolít le (ami mikrozetés esetén tipikus), akkor átlagosan ® sem veszít semmit egy hagyományos mikrozetési séma használatához képest. A [18]-os cikk által javasolt ösztönz® séma alapötlete, hogy a csomag forrása egy elektronikus lottószelvényt csatol a csomaghoz, mely egy meghatározott p valószín¶séggel nyer® szelvény bármely továbbító eszköz számára, ahol p egy rendszerparaméter, amit a hálózati szolgáltató állít be. Minden, a csomagot továbbító eszköz ellen®rzi, hogy számára a csatolt szelvény nyer®-e vagy sem. A nyer® szelvényeket a továbbító eszköz tárolja. Az eszköz a nyer® szelvénnyel együtt azt is megjegyzi, hogy a szelvényt tartalmazó csomagot melyik eszközt®l kapta és melyik eszköznek küldte tovább. Az összegy¶jtött nyer® szelvényeket, valamint a velük együtt tárolt eszköz-azonosítókat az eszköz egy kés®bbi id®pontban, kötegben átadja a hálózati szolgáltatónak (pl. mikor az eszköz zikailag közel kerül egy bázisállomáshoz és így közvetlenül el tudja a köteget küldeni a bázisállomásnak). A bázisállomás a köteget a hálózati szolgáltató számlázó központjába


41

küldi. Mikor egy csomag megérkezik a bázisállomáshoz, a bázisállomás ellen®rzi a csomaghoz csatolt lottószelvény érvényességét (a lottószelvény nem más, mint egy üzenethitelesít® kód, melyet a forrás és a hálózati szolgáltató közötti titkos kulcs segítségével számol ki a forrás és ellen®riz a bázisállomás). Ha a szelvény érvényes (azaz valóban a csomag forrása generálta), akkor a csomagot a bázis állomás továbbítja a cél felé. Ellenkez® esetben a bázisállomás eldobja a csomagot, hiszen annak továbbításáért nem tud megterhelni senkit. A sikeres csomagokról a bázisállomás tájékoztatja a hálózati szolgáltató számlázási központját. A számlázási központ tehát két forrásból kap információt: egyrészt a bázisállomások tájékoztatják, hogy mely csomagok érték el sikeresen a célt, másrészt a továbbító eszközök küldik el nyer® lottószelvényeiket. A számlázási központ ezen információk összevetésével állapítja meg, hogy kit kell megterhelni, kit kell kizetni, és hogy ki próbált meg csalni. Egészen pontosan: a sikeres csomagok forrásának számláját a központ megterheli. A terhelés mértékét a hálózati szolgáltató állapítja meg, ám az alapvet®en a csomag méretét®l függ. A nyer® szelvényekre csak akkor zet a központ, ha a szelvényhez tartozó csomagot valamely bázisállomás jelentette, azaz az sikeresen elérte a célt. Ez ösztönzi az eszközöket, hogy továbbítsák a csomagot, különben nem kapnak zetséget, hiába rendelkeznek nyer® szelvénnyel. Ráadásul mikor egy nyereményt kizet a központ, akkor nem csak a nyer® szelvényt benyújtó eszköznek zet, hanem annak eszköznek is, amelyt®l a szelvényt benyújtó eszköz a csomagot kapta, és annak is, akinek a csomagot továbbküldte. Ez még jobban ösztönzi az eszközöket a csomagok továbbítására, hiszen így még vesztes szelvényt tartalmazó csomagokat is van értelme továbbítani, mivel ugyanaz a szelvény a következ® eszköz számára lehet nyer®, mely esetben a nem nyer® továbbító eszköz is jutalomban részesül. A fentieken túl, a szomszédok nyer® szelvénnyel együtt történ® lejelentésének van egy másik el®nye: lehet®vé teszi a központ számára csomagtovábbítási statisztikák készítését. Az ezen statisztikákban felfedezett inkonzisztencia pedig lehet®vé teszi a csalások detektálását, majd megbüntetését. Ha például egy eszköz szisztematikusan megtagadja a csomagok továbbítását, akkor nagyobb gyakorisággal fog megjelenni csomagot fogadó szomszédként, mint csomagot küld® szomszédként. Ráadásul, minél agresszívebben tagadja meg egy eszköz a csomagok továbbítását, annál könnyebben és hamarabb fogja ezt a számlázási központ detektálni.


42

3.2.4. Példa hírnév alapú ösztönzési sémára A hírnév alapú ösztönt® sémák általában a hálózati rétegben kerülnek alkalmazásra, ezért els®sorban az útválasztási és csomagtovábbítási problémák kiküszöbölésére szolgálnak. A [21]-es cikkben egy olyan megoldást találunk, melyben a helytelenül viselked® csomópontokat kizárják a hálózatból egy ún. watchdog és egy ún. pathrater alkalmazása segítségével. A szerz®k a Dynamic Source Routing algoritmust kiegészítend® tervezték meg ezt a két alkalmazást, mely segít felderíteni a hálózatban a rosszindulatú eszközöket. A watchdog egy egyszer¶ meggyel®, amelyik minden csomópontba bele van építve és gyeli a továbbított csomag útját egy következ® ugrás erejéig. Vagyis miután egy A szenzor továbbküldte a csomagot a B szenzornak, gyeli, hogy B továbbítja-e a csomagot C-nek (feltéve, hogy a csomag útja tartalmazza mind az A, mind a B és a C szenzorokat). Ha nem alkalmazunk titkosítást, akkor A azt is meg tudja mondani, hogy B az eredeti fejlécet és a hozzá tartozó tartalmat küldte-e tovább, vagy változtatott a csomagon. A gyelés egészen pontosan úgy valósul meg, hogy A egy átmeneti tárolóban (puerban) raktározza a legutóbbi néhány B-nek küldött üzenetet, majd minden egyes áthallásnál (amikor B adásaiba belehallgat) megvizsgálja, hogy az aktuális küldött csomag benne van-e a puerban. Ha benne van, akkor a csomag továbbításra került B által, ezáltal a puerb®l kivehet®. Ha nincs egyezés és a csomag sokáig a puerban marad, akkor B-nek egy megrovó bejegyzés kerül a számlájára, ami valójában a B-t értékel® valós szám csökkentését jelenti, ami B hírneve. Sajnálatos módon számos problémával kell az algoritmusnak szembenéznie. El®fordulhat például, hogy A egyszerre szeretne B adásába belehallgatni és üzenetet kapni egy másik szenzortól. Ez ütközéshez vezet, ami meggátolja A-t B adásának gyelésében. A nem tudhatja ekkor, hogy B adása ütközött-e egy saját szomszédjának csomagjával vagy két saját szomszédja próbált meg egyszerre kommunikálni vele és az okozta az interferenciát. Ilyenkor A-nak tovább kell gyelnie B-t és ha ez többször is el®fordul, akkor valószín¶sítheti, hogy B rosszindulatúan viselkedik. Hasonló ütközés léphet fel C-nél is, amikor például csomagot kap B-t®l és ezzel egyid®ben egy másik szomszédjától is. Ekkor B rosszindulatúan megtagadhatja a csomag megismétlését és A nem fog tudomást szerezni a csalásról. Ha B tisztán rosszindulatú, akkor azt is elérheti, hogy C-hez biztos ne jusson el a csomag, egyszer¶en csak akkor kell adnia, amikor C egy másik szomszédja is ad. Tekintve azonban, hogy ez a viselkedés B-


43

nek hasznot nem hoz és spórolni sem tud vele (s®t, inkább energiát fogyaszt azzal, hogy megpróbálja a megfelel® adási id®pontot megtalálni), a gyakorisága miniális lesz. Elképzelhet® olyan támadás is a watchdog ellen, hogy B olyan kicsire állítja a küldési energiáját, hogy A még éppen bele tudjon hallgatni az adásába, de C-hez már ne jusson el a csomag (feltételezve, hogy A közelebb van B-hez, mint C). Ekkor A nem küld negatív értékelést B-r®l annak ellenére, hogy C nem kapta meg a csomagot. Ez azonban B részér®l addícionális információk birtoklását feltételezi, hiszen B-nek tudnia kell, melyik szomszédja milyen távol helyezkedik el t®le. A watchdog algoritmus m¶ködése közben szétárasztással közli a hálózat résztvev®ivel a többi résztvev® hírnevét (az említett valós számot). A pathrater alkalmazás ezen számok alapján építi ki az utakat az alábbi módon. A pathrater minden szenzorban fut és az ismert értékelések alapján választja ki a megfelel® utat a csomagok számára. Egy út értékelése az utat alkotó szenzorok értékeléseinek átlaga. Ez a számolási mód lehet®séget ad egyrészt a különböz® utak összehasonlítására, másrészt emulálni tudja a legrövidebb út algoritmusát, amennyiben mégsem ismertek a szenzorok értékelései. A több megfelel® út közül az algoritmus a legmagasabb értékelés¶t választja. Általában ezek az értékelések 0 és 1 közötti értéket vesznek fel, azonban −100 lesz az értékelésük azoknak a szenzoroknak, melyekr®l feltételezzük, hogy rosszindulatúan viselkednek (akár csalnak, akár spórolni akarnak, akár tisztán ártó szándékúak). Amikor a pathrater kiszámolja egy út értékelését, a negatív érték arra fog utalni, hogy az úton rosszindulatú szenzorok találhatóak. Mivel el®fordulhat, hogy a szenzor csak ideiglenes hibás m¶ködés vagy pillanatnyi er®forráshiány miatt viselkedett látszólag rosszindulatúan, nem kellene végleg kizárni a hálózatból. Ezért a negatív értékelés¶ szenzorok értékelése id®vel lassan magától javul. A Dynamic Source Routing ezirányú kiterjesztése a szerz®k teszteredményei szerint 17%-kal javította a hálózat átereszt®képességét alacsony mobilitási szint mellett és 40%nyi rosszindulatúan viselked® csomópontot feltételezve és 27%-kal magas mobilitás mellett.

3.3. Kooperáció ösztönzés nélkül Az eddigiek során láthattuk, hogy a szenzorhálózatokban a kooperáció célravezet® eszköz, ha a célunk a szenzorhálózat élettartamának maximalizálása. Számos cikk foglalkozik olyan keretrendszerek kidolgozásával, melyben a kooperáció kizet®d®, vagyis racionális


44

viselkedési forma. Ezeket a keretrendszereket nevezzük ösztönz® sémáknak. Az el®z® fejezetb®l kiderült, hogy az ösztönzés lehet számla alapú, amikor a továbbító csomópontok virtuális pénzt kapnak a csomag továbbításáért, vagy hírnév alapú, amikor a csomópontok hírneve romlik, ha nem vesznek részt a forwardolási láncban. Azonban, ha a kooperáció tényleg célravezet® az élettartam maximalizálása szempontjából, akkor mi szükség van az ösztönzésre? Ebben a munkában azt szeretném bemutatni, hogy az esetek nagy részében semmi. Az általam vizsgált modellekben, szimmetrikus interakciós sémát feltételezve a kooperáció a szenzorok önérdekére alapozva is kialakul az esetek túlnyomó többségében ezt nevezzük spontán kooperációnak. Persze ehhez arra van szüségünk, hogy a szenzorok tisztában legyenek azzal, hogy nekik a maximális élettartamra kell törekedniük, és emellett el kell tudniuk végezni a kiszabott mérési feladatukat is. Az önérdekre alapozott kooperáció legszebb jellemvonása az, hogy a nem kooperatív viselkedés kizárására szolgáló ösztönz® és büntet® sémák használata fölöslegessé válik, ami által jelent®sen csökkenhet a hálózati nem hasznos adatforgalom (overhead), hiszen nem lesz szükség a virtuális érmék küldözgetésére és a hírnevek kezelésére. A hálózat m¶ködése egyszer¶södik, tervezési ideje pedig lerövidül. Az irodalomban még nem nagyon található a spontán kooperáció kérdéskörével foglalkozó anyag. [25]-ben a szerz®k ugyan ezzel a témakörrel foglalkoznak, viszont vizsgálataik alapja az ad hoc hálózatok témaköre, nem pedig a szenzorhálózatok. Ezenkívül a cikkben a hálózat résztvev®it energiaosztályokba sorolják, ami azok heterogenitására utal, miközben az én modellemben minden csomópont ugyanolyan energiaforrásokat birtokol. Végezetül [25]-ben véletlenül választott eszközök kommunikálnak egymással, míg itt minden csomópont kommunikál a bázissal. A [26]-os cikkben a szerz®k azt vizsgálták, hogy milyen körülmények között válik az ösztönzés nélküli kooperáció a legjobb megoldássá statikus ad hoc hálózatokban. Már gyelembe vették a hálózat topológiáját is, nem úgy, mint [25]-ben. Az általam vizsgált modellhez képest a legnagyobb különbség az, hogy a szerz®k nem számoltak az eszközök energiafogyasztásával, miközben az én munkámban ennek központi szerepe van. A vizsgálat tárgyát tekintve a [24]-es cikk áll legközelebb a munkámhoz, mindazonáltal számos különbséget kell kiemelnem. El®ször is, az említett cikkben a hálózat minden sikeres kör végén kap kizetést (vagyis minden olyan körben, amikor legalább elégséges számú csomag beérkezett a bázisra), ami egy szubjektív érték és az adott kör fontosságát jellemzi. Az általam használt modellben nincs a körök végén kizetés (payo), mindössze a játék végén


45

a hálózat élettartama min®sül annak. Másodszor, mi megkövetelünk egy minimális QoS-t (Quality of Service-t), amit azzal érünk el, hogy bizonyos esetekben kötelez® érvénnyel sikeresen végz®d®, ugyanakkor nem feltétlenül kooperatív lépést írunk el®. Ez egy természetes kritérium, amit az alkalmazandó szenzorhálózatoktól is elvárnánk, a [24]-es cikkben mégsem szerepel. Harmadszor, mi sokkal nagyobb mozgásteret hagyunk a szenzoroknak, ami a stratégia ill. a lépések kiválasztását illeti (b®vebben lsd. a 4. és az 5. fejezetben), míg a cikkben a lépésválasztás bináris döntés, ami csak az utolsó lépés sikerességét®l függ. Megemlíteném, hogy a cikkben a hálózat élettartamát másképp deniálják a szerz®k, mint ahogy az általam használt modellben az meg van határozva, hiszen a hálózatot addig tekintik él®nek, amíg az összes szenzor életben van, míg esetemben egyetlen él® szenzor is él® hálózatot ad. Végül arra is kitérnék, hogy az általam használt modell egy ponton sz¶kebb, mint a cikkben leírt szimulátor: én csak azt az esetet vizsgáltam, amikor egy vagy több közös bázisállomás felel®s a hálózat összes mért adatának begy¶jtéséért, míg a cikkben ezen kívül a szeparált bázisállomások szimulációja is megtalálható. Eddig is többször említettem már a játék, a kör és a kizetés szavakat. Ezek mind játékelméleti fogalmak, amelyek nagyon fontosak lesznek számunkra. A spontán kooperáció vizsgálatának játékelméleti alapokra helyezése természetesen adódó lépés, hiszen tipikus játékelméleti sémával állunk szemben: individuális résztvev®k egymással ellenkez® érdekeit kell összehangolnunk egy globális cél érdekében. Az 5. fejezett®l kezdve már a konkrét modellr®l és a vizsgálati eredményeimr®l lesz szó, azok megértéséhez azonban rövid kitér®t kell tennünk a játékelmélet világába.

4. fejezet Játékelméleti eszköztár Ahhoz, hogy használni tudjuk a játékelmélet nyújtotta lehet®ségeket, el®ször meg kell ismerkedni a tudományág fogalomrendszerével. Egy stratégiai formájú játékot egy {N, S, U } hármassal adhatunk meg, ahol N a játékosok halmaza, S a stratégiák halmazainak halmaza, U pedig a játékosok hasznossági függvényeinek halmaza. Egy s ∈ Si stratégia egy függvény, amely az i. játékosnál a játék egyes állapotaihoz lépéseket rendel. Egy u ∈ U hasznossági függvény kvantitatív mér®számot rendel a játék végeredményeihez. A játék során egy játékos akkor jár a legjobban, ha a számára legjobb stratégáit játsza, vagyis azt, amelyiknek a hasznossága a legnagyobb. A legjobb stratégia kiválasztása gyakran csak utólag végezhet® el. Ekkor egy adott kizetési mátrixban szerepl® értékek alapján hozhatjuk meg a döntést az optimális stratégiára vonatkozóan. Célunk tehát egy olyan stratégia megtalálása, amely szerint játszva (ha a másik fél is egy meghatározott stratégiát játszik) a saját szenzorhálózatunk a lehet® legtovább életben marad.

4.1. Domináns stratégiák Tegyük fel, hogy adottak a stratégiapárok és a rájuk jellemz® élettartamok, célünk pedig az optimálisnak mondható stratégiák megtalálása az adott stratégiatérben. Ehhez a legkézenfekv®bb módszer a domináns stratégia keresése. Ez a módszer egy kizetési mátrixával adott játékban keres optimális stratégiákat. Ebben a modellben nem beszélhetünk kizetési mátrixról, mivel itt a szenzorok nem kapnak jutalmat. Az ellentmondás feloldására bevezettük az élettartam mátrix elnevezést. Az élettartam mátrixban minden sor és minden oszlop megfelel egy-egy stratégiának, a mátrix 46

4. FEJEZET. JÁTÉKELMÉLETI ESZKÖZTÁR

47

elemei pedig az adott két stratégiával egymás ellen játszó szenzorhálózatok élettartamai, vagyis (L1 , L2 ) alakú kifejezések, ahol L1 az els® játékos élettartama, L2 a másodiké. A módszer lényege, hogy a játékosok gondolatban felváltva kihúzogatják azokat a sorokat ill. oszlopokat a mátrixból, amelyiknél van minden eshet®séget gyelembe véve jobb stratégia. Ha például az 1. játékos úgy találja, hogy az ® második stratégiáját (a mátrix második sorát) minden elemében dominálja az els® stratégia (a mátrix els® sora), akkor a második sor kihúzható a mátrixból. Ha további ilyen sorokat is talál, akkor azokat is kihúzza, majd a 2. játékos következik, aki a már megcsonkított mátrixot fogja vizsgálni, de az oszlopok irányából. Vagyis, ha a 2. játékos talál olyan oszlopot, amelyik legalább egy elemében kisebb és a többi elemében sem nagyobb egy másik oszlopnál, akkor azt az oszlopot kihúzhatja. Nyilván több oszlop is kihúzható egy lépésben. Ha már nincs több eltávolítható oszlop, akkor újra az 1. játékos fogja vizsgálni a már többszörösen redukált mátrixot és így tovább. A redukció akkor ér véget, ha már egyik játékos sem tud egyetlen mátrixelemet sem eliminálni. A 4.1. ábrán egy-egy példát láthatunk sikeresnek mondható és kevésbé sikeres domináns stratégia keresésre. A bal oldali oszlopban tudtunk találni domináns stratégiát, mert a mátrix tartalma lehet®vé tette ezt. Három lépésben megkaptuk, hogy az 1. játékos akkor jár jól, ha a D stratégiát választja, míg a 2. játékos akkor, ha az A stratégia lépéseit követi. A jobb oldali oszlopban a mátrixot kicsit megváltoztattam: az els® sor harmadik oszlopában a 10-es értéket 13-ra cseréltem. A domináns egyensúly keresése rögtön kudarcba fulladt. Az általam használt modellekben a játék élettartam mátrixa nem ilyen egyszer¶ szerkezet¶, hiszen minden cellában két élettartam szerepel, ami egyben azt is jelenti, hogy az 1. játékos a cella els® bejegyzését gyelné a dominancia vizsgálatakor, míg a 2. játékos a második bejegyzést. A leírt példa is értelmezhet® ebben a formában, ha úgy tekintjük, hogy minden cellába kétszer írjuk be ugyanazt a számot és mindkét játékos számára a nagyobb értékek az impozánsabbak. A szimulációk eredményeit tehát el®ször egy olyan rutinnal vizsgáltuk, amely az élettartam mátrixban megkereste a domináns stratégiákat. Sajnos az eredmények elszomorítóak voltak: az élettartam mátrix majd' teljes egészében domináns stratégiákat tartalmazott. A probléma az volt, hogy egyrészt sok olyan stratégiapár volt, melyek egymáshoz képest azonos eredményt értek el, és ezeket az általánosság megsértése nélkül nem lehetett kizárni. Másrészt az is el®fordult, hogy sorok ill. oszlopok között nem lehetett preferenciarelációt felállítani, mert mondjuk az i. sor els® eleme nagyobb volt a j . sor els® eleménél, viszont


2. játékos

1. játékos

A

1. lépés

B C D

A 12 8 10 5 B 10 7 10 2 C 13 4 12 9 D 14 10 11 6 2. játékos

1. játékos

A

B 10 7 10 2 C 13 4 12 9 D 14 10 11 6

3. lépés

A 12 8 13 5 B 10 7 10 2 C 13 4 12 9

2. játékos A

B C D

A 12 8 13 5 B 10 7 10 2 C 13 4 12 9 D 14 10 11 6

2. játékos A

1. játékos

2. lépés

B C D

A 12 8 10 5

B C D

D 14 10 11 6

1. játékos

2.lépés

2. játékos A

1. játékos

1. lépés

48

B C D

A 12 8 10 5 B 10 7 10 2 C 13 4 12 9 D 14 10 11 6

4.1. ábra. Példa domináns egyensúly számolására

a második elemekre ennek a fordítottja volt igaz. Ezeket a sorokat és oszlopokat ezzel a módszerrel nem lehet eltávolítani. Látható tehát, hogy a domináns stratégia fogalma nem felelt meg az elvárásainknak,


49

más megoldási módszert kellett keresni. Egyszer¶en adódott, hogy a másik leggyakrabban használt módszert, a Nashegyensúly keresését kellene alkalmazni.

4.2. Nashegyensúly Egy stratégiahalmaz Nashegyensúlyban van, ha egyik játékos sem tud a jelenleginél magasabb élettartamot elérni, ha a többi játékos nem változtat a stratégiáján. Formálisan:

G = (N ; S1 , . . . , Sn ; U1 , . . . , Un ) játék Nash-féle egyensúlypontja minden olyan x∗ = (x∗1 , . . . , x∗n ) ∈ S1 × . . . × Sn vektor, amelyre tetsz®leges k ∈ [1..n], xk ∈ Sk esetén Uk (x∗1 , . . . , x∗k , . . . , x∗n ) ≥ Uk (x∗1 , . . . , xk , . . . , x∗n ), ahol n a játékosok száma. Két játékos esetére egyszer¶sítve azt kapjuk, hogy olyan stratégiapárokat keresünk, melyekre igaz, hogy csak akkor tudna az egyik játékos ezen stratégia végeredményénél jobban kijönni a játékból, ha a másik játékos is változtatna a stratégiáján. A Nashegyensúly keresése szintén az élettartam mátrix alapján történik. Minden sort egyenként végignézünk és kiszemeljük mindenhol a sorjátékosra vonatkozó elemek közül a legnagyobb elemeket. Utána elvégezzük ugyanezt az oszlopokra is, vagyis tulajdonképpen a második játékos is ugyanazt végrehajtja, amit az els®. A két játékos által kijelölt maximumokat összevetve, ha van olyan cella, melyet mindketten kiszemeltek, akkor az egy Nashegyensúlyi stratégiapár. A 4.2. ábrán a Nashegyensúly keresésére láthatunk egy példát. A 4.1. ábrán már látott két mátrixon végeztem el kézzel az egyensúlyok meghatározását. Az els® lépésben mindkét oszlopban az 1. játékos választja ki a sorok maximumait (ezeket téglalappal jelöltem), majd a 2. játékos határozza meg az oszlopok maximumait (körökkel jelölt értékek). A bal oldali oszlopban azt kaptam, hogy egyedül a DA stratégiapár alkot Nashegyensúlyt, míg a másik mátrixban két ekvilibrium is található (téglalappal és körrel egyidej¶leg jelölt cellák). Nashegyensúlyt keresve mindvégig azzal a biztos tudattal dolgozhatunk, hogy nem maradnak vissza az el®z® módszerhez hasonlóan esetleg nagyobb mátrixdarabok, amikkel nem tudunk kezdeni semmit. Itt a megoldáshalmaz mindig diszkrét elemek összessége (ami persze jelentheti a mátrix egy jelent®sebb összefügg® részét, de ez már kezelhet®). Sajnálatos módon a modellt tanulmányozva arra jutottam, hogy rengeteg Nashegyensúllyal kell megküzdenem. Meggyeléseim alapján a kés®bb tárgyalandó vektorsúlyos modellben n stratégia esetén hozzávet®leg

n2 3

Nashegyensúlyi stratégiapár van. Ez azt jelenti, hogy az


2. játékos

1. játékos

A

1. lépés

A 12 8 10 5 B 10 7 10 2 C 13 4 12 9

A

D 14 10 11 6 2. játékos

1. játékos

A

A 12 8 13 5 B 10 7 10 2 C 13 4 12 9

2. lépés

2. játékos

B C D

A 12 8 10 5 B 10 7 10 2 C 13 4 12 9 D 14 10 11 6

B C D

D 14 10 11 6

A 1. játékos

2. lépés

2. játékos

B C D 1. játékos

1. lépés

50

B C D

A 12 8 13 5 B 10 7 10 2 C 13 4 12 9 D 14 10 11 6

4.2. ábra. Példa Nashegyensúly meghatározására

n × n-es élettartam mátrixban átlagos majdnem minden harmadik elem Nashekvilibrium. Kés®bb látni fogjuk, hogy véletlenszer¶en elhelyezett szenzorok esetén a Nashegyensúlyok száma már nem ilyen nagy, de ahhoz még túl sok, hogy a végeredményt jól értelmezhet®nek mondhassuk.

4.3. Maximális Nashegyensúly Az eredményhalmaz terjedelmessége ellenére is bíztatónak t¶nt azonban a Nashegyensúlyi módszerek segítségével történ® optimális stratégia keresés. Itt az eredményhalmaz elemei egyszer¶ stratégiapárok, melyek mind megfeleltek a támasztott követelményeknek és nem olyan határozatlan min®ség¶ mátrixtöredékek, mint amiket a domináns stratégiák keresése közben kaptunk.


51

Könnyen adódik tehát a gondolat, hogy a kapott Nashegyensúlyok közül azokat a stratégiapárokat kellene kiválasztani, melyek legjobban kielégítik az elvárásainkat, vagyis maximális élettartamot garantálnak. Nyilván most nem lehet egyoldalúan a saját szenzoraink élettartamának maximalizálásáról beszélni, hiszen a Nashekvilibriumok mindkét fél számára ideálisak. Említett szelekciót elvégezve kapjuk meg a maximális Nash egyensúlyokat. A válogatás a következ®képpen zajlott: adottak voltak a Nashoptimális stratégiapárok (vagyis a megfelel® mátrix cellák), melyek (L1 , L2 ) alakúak. Egy stratégiapár kizárható a maximális Nashhalmazból, ha van olyan másik stratégiapár a halmazban, melyre igaz, hogy mind az L1 , mind az L2 értéke nagyobb. Utóbbi stratégiapárral tehát mindkét szenzor tovább tudna élni. Természetesen azok a stratégiapárok is elhagyhatóak, melyek esetében az egyik élettartam kisebb, a másik pedig egyenl® egy jobb Nashegyensúlyi stratégiapár által kínáltnál. Megemlítend®, hogy nem céltalan az a gondolat, hogy a másik (ellenfél, konkurens cég által üzemeltetett) szenzorhálózat élettartamát is érdemes gyelni. Ugyanis amíg az a szenzorhálózat is él, addig van esélyünk arra, hogy olcsón juttassuk el az információt a bázisállomáshoz, míg annak halála után önállóságra vagyunk kényszerítve. Mivel a önálló munkavégzés költsége jelent®sen nagyobb a kooperációnál, a saját szenzoraink sem fogják sokkal túlélni az ellenfél szenzorait.

5. fejezet Az egyszer¶sített modell A problémát egy egyszer¶sített modellen kezdtem el vizsgálni, amit az alábbi kétszerepl®s játék ír le. A játékosokat a továbbiakban Fehérnek és Feketének hívom. A játékot körökre osztva játszák. Minden körben mindkét játékosnak egy egyszer¶ feladatot kell végrehajtania. A feladatot végrehajthatják önállóan, vagy a másik játékos segítségével. A feladatot drágább egyedül végrehajtani, de biztos a siker, míg kooperálva olcsóbb, de bizonytalan a siker. Az önálló m¶ködés közvetlen küldést jelent, míg a kooperáció egy küldést a szomszédnak, és egy kérést a szomszéd felé, hogy továbbítsa az adatokat. Ez alapján a Fekete játékosnak minden kör elején az alábbi döntéseket kell meghoznia:

• kér-e segítséget a Fehér játékostól a saját feladatához • ha a Fehér kér t®le segítséget, akkor segít-e neki Természetesen a Fehér játékosnak ugyanezeket a döntéseket kell meghoznia, tehát mindkét játékosnak minden körben négy lehet®sége van:

• CC Cooperate/Cooperate: segítséget kér a saját feladatához, és segít, ha kérik t®le • CD Cooperate/Defect: segítséget kér a saját feladatához, de nem segít a másiknak • DC Defect/Cooperate: nem kér segítséget a saját feladatához, de segít, ha a másik kéri

• DD Defect/Defect: nem kér segítséget a saját feladatához, és nem is segít a másik félnek 52

5. FEJEZET. AZ EGYSZERSÍTETT MODELL

53

A résztvev®k elhelyezkedését és a küldések költségeit az 5.1. ábra szemlélteti. Ez a legegyszer¶bb olyan elrendezés, amelyben csak egy bázist alkalmazunk és a kooperáció kialakulhat mindkét játékosnál. Tisztázandó, hogy most is és a kés®bbi, bonyolultabb elrendezéseknél is a játékosok fogalma a szenzorokat birtokló hatóságokat takarja. Egy játékos tehát több szenzor fölött rendelkezik, viszont körönként csak egy lépést választ, és minden szenzor azt fogja lépni.

2

α

2

1

1

1

1

α

1

1

1

1

5.1. ábra. A vizsgált egyszer¶ hálózat

A játékosok számára a feladat elvégzése (csomagok eljuttatása a bázishoz) lehet 2 egység költség¶ körönként, amennyiben segítséget kérnek a másik félt®l és az segít. Ha nem kérik a másik fél segítségét, akkor 2α + 1 költséggel kell számolniuk csomagjaik kapcsán. Ha azonban még a másik játékos segítségkérését is kielégítik, akkor további 1 egységnyi költséggel szembesülnek. A segítségkérés visszautasítása ingyenes. A különböz® lépéspárok el®fordulása esetén jelentkez® költségeket az 5.1. táblázat tartalmazza. A cellákban az els® érték felel meg a sor elején lév® lépést választó játékos költségének, míg a második érték az oszlopot meghatározó lépés költsége. A költségek a szenzorok költségeinek összegei: a távolabbi szenzorok 1 egységet fogyasztanak C* lépés esetén és 2α egységet D* lépés esetén, míg a bázishoz közelebb lév® szenzorok a saját csomagjuk beküldésére 1 egységet fordítanak, ill. ha érkezik hozzájuk segítségkérés és *C az aktuális lépés, akkor további 1 egységet áldoznak a segítségre. A játékosok mindkét szenzora egy-egy B büdzsével gazdálkodik, ami azok energiatartalékát modellezi. Ebb®l a B büdzséb®l tudja nanszírozni a szenzor a lépéseit. Ha egy szenzornak elfogy a büdzséje, akkor az a szenzor kikapcsol. A sikeres feladat-végrehajtáshoz mindkét szenzor csomagjára szüksége van a bázisnak, így egy szenzor halála egyben saját


54

5.1. táblázat. A játékosok lépésköltségei CC

CD

DC

DD

α

CC

3, 3

3, 2

2, 2 + 2

2, 2α + 1

CD

2, 3

2, 2

2, 2α + 2

2, 2α + 1

DC

2α + 2, 2 2α + 2, 2 2α + 1, 2α + 1

2α + 1, 2α + 1

DD

2α + 1, 2 2α + 1, 2 2α + 1, 2α + 1

2α + 1, 2α + 1

hálózatának halálát is jelenti. Ha a másik játékos szenzorainak még van felhasználható egysége, akkor tovább tud m¶ködni a hálózata, de ha kér is segítséget, soha nem kap, s®t arról sem fog tudomást szerezni, hogy kérésének elutasítása a másik fél lemerülésére vagy önzésére vezethet®-e vissza. A hálózatok élettartama a játszott körök száma, amíg tart a szenzorok büdzséje. Mindkét játékos célja saját hálózata élettartamának maximalizálása. Ha a játék csak ennyi lenne, akkor nagyon egyszer¶ lenne a megoldása. Mindkét játékosnak CD-t kellene játszania folyton, így minden körben csak két egységet fogyasztana a hálózatuk. Ez pont

B 2

hosszú életet jelentene. Ezzel csak az a baj, hogy soha nem sikerülne

egyik feladatot sem végrehajtaniuk, hiszen ahhoz szükség van a távoli szenzor mérési eredményeire is, CD lépés esetén azonban a közeli szenzorok nem továbbítják a csomagokat, így azok nem érnek el a bázisállomáshoz. Ennek így nem sok értelme lenne. Be kell tehát vezetni még valamilyen feltételt. Ez a feltétel az elvárt sikerességi ráta, ami egy rendszerparaméter az adott intervallumon belüli sikeres körök minimális számára vonatkozóan. Ehhez kapcsolódó fogalom a sikerességi ráta, ami a sikeresen elvégzett feladatok száma osztva az összes feladat számával az adott id®intervallumban. Egy körben egy feladat végezhet® el, ezért a sikerességi ráta egyben a sikeres körök száma osztva az adott id®intervallumba es® körök számával. Egy kört akkor tekintünk sikeresnek, ha a játékos mindkét szenzorának mérési adata eljutott a bázishoz. Ha a sikerességi ráta a következ® lépésben az elvárt szint alá csökkenhet, akkor a játékos nem kockáztathat: mindenképpen olyan lépést kell tennie, ami sikeres lesz. Ez a lépés lehet DC vagy DD, röviden D*. Ezt nevezzük kényszerhelyzetnek. Ha ezt a szabályt betartja a játékos, akkor biztosan nem csökken a sikeressége (sikerességi rátája) a kívánt szint alá. Jelöljük a sikerességi ráta alsó korlátját (vagyis az elvárt sikerességi rátát) ρ-val. Legyen

w az utolsó lépések eredményét tartalmazó ablak (history, el®élet) hossza, s az ablakban


55

lév® sikerek részaránya (vagyis a sikerességi ráta). Az ablakban a sikereket (sikeres köröket) 1-ekkel jelöljük, a sikertelen köröket 0-ás bejegyzéssel. Ha az s < ρ eset el®fordulhat a következ® lépésben, akkor a játékos kényszerhelyzetbe került. Kényszerhelyzetben a játékos valamilyen D* stratégiát választ. Az ablak mérete és az elvárt sikerességi ráta a rendszer paramétere. A nagyobb ablak és a kisebb ráta nagyobb szabadságot ad a rendszernek, míg a kisebb ablak és a magasabb ráta egy szigorúbb rendszert ír le. Figyeljük meg a sikerességi ráta és az elvárt sikerességi ráta közötti különbséget. A sikerességi ráta (s) a játék folyamán változik, értéke minden pillanatban a history-ban lév® sikeres körök számától függ. Az elvárt sikerességi ráta (ρ) egy rendszerparaméter, ami azt a minimális sikerességi szintet adja meg, ami alá nem mehet soha a sikerességi ráta. Tehát a játékosok célja a hálózatuk élettartamának maximalizálása gyelembe véve az elvárt sikerességi rátát is.

5.1. A kétlépéses stratégiák A vizsgálatokat a lehet® legegyszer¶bb stratégiákkal kezdtem. A stratégiateret analítikusan vizsgáltam. A stratégiák mindig egy adott lépést (CC, CD, DC vagy DD) választanak, amit®l csak akkor térnek el, ha a sikerességi rátájuk veszélybe kerül. Ekkor egy másik adott D* lépés szerint játszanak. Ennek megfelel®en minden ebbe az osztályba tartozó stratégia maximum két lépéssel leírható, azaz egy stratégia egy {m m0 } lépéspárral adható meg, ahol m az a lépés, amit akkor alkalmaz a játékos, ha nincs kényszerhelyzetben és m0 az a lépés, amit kényszerhelyzetben választ. Ha m egy D* lépés, akkor a stratégia soha nem kerülhet kényszerhelyzetbe, tehát elég, ha csak egy lépésb®l áll. A felsorolásban {m m0 } ill. m alakban írom le a stratégiákat. A vizsgált stratégiák: 1. CC DC (Segít®kész) 2. CC DD (Szigorú) 3. CD DD (Kihasználó) 4. DC (Naív) 5. DD (Magánzó)


56

Még lehet®ség lenne CD DC, DC DD és DD DC stratégiákra, de ezeket a stratégiákat nem vizsgáltam. A CD DC nem racionális stratégia, mert éppen kényszerhelyzetben segít®készebb. A DC DD és a DD DC nem különbözik a tiszta DC illetve DD-t®l, mivel egy D* stratégia soha nem juthat kényszerhelyzetbe. Ezt az öt stratégiát egymással összevetve, analítikusan elemezve megkaptam a kétlépéses stratégiák körében értelmezett élettartam mátrixot. Ezen el®ször domináns stratégiákat kerestem, majd a kapott redukált mátrixban elvégeztem a Nash-egyensúlyi vizsgálatot.

5.1.1. A kétlépéses stratégiák vizsgálati eredményei Az 5.2. táblázat tartalmazza a különböz® stratégiák várható élettartamát, ha egymással találkoznak. Az eredmények nem veszik gyelembe a kezdeti tranziens lépéseket (ezekr®l kicsit lejjebb), mivel azok elhanyagolhatók a teljes id®tartamhoz képest. Az els® érték a sor, a második az oszlop játékosra vonatkozik. Jelölések:

• B büdzsé • α a távolság és a teljesítmény közti hatványtényez® W = dα • R = ρ(2α + 1) + (1 − ρ)2, csak az egyszer¶sített írásmód miatt alkalmazom • A = 2α + 1, csak az egyszer¶sített írásmód miatt alkalmazom

1 1 2 3 4 5

B ; B3 3 B ; B3 3 B(2R−1) B ; R+1 R(R+1) B ; B(A+R−1) A+1 (A+1)R B ; B A R

5.2. táblázat. Paraméteres élettartamok 2 3 B 3 B 3 B R

; B3 ; B3 ; B R B(A+R−1) B ; (A+1)R A+1 B ; B A R

; B(2R−1) R(R+1) B ; B R R B B ; R R B(A+R−1) B ; (A+1)R A+1 B ; B A R B R+1

4

B(A+R−1) B ; A+1 (A+1)R B(A+R−1) B ; A+1 (A+1)R B(A+R−1) B ; A+1 (A+1)R B ; B A A B B ; A A

5 B R B R B R B A B A

; ; ; ; ;

B A B A B A B A B A

A következ® lépés, hogy megnézzük, van-e olyan stratégia, amit valamelyik másik dominál minden esetben. A CC DD (Szigorú, 2.) stratégia mindig legalább olyan jól jár, mint a CC DC (Segít®kész, 1.) stratégia, így ki lehet húzni a táblázatból a CC DC stratégiát.


57

Ezután a DD (Magánzó, 5.) mindig legalább olyan jó, mint a DC (Naív, 4.), így a DC-t is ki lehet húzni. A CC DD mindig legalább olyan jó mint a DD, hiszen A > 3 és A > R miatt

B(A+R−1) (A+1)R

>

B A

mindig teljesül. Tehát a DD-t is ki lehet húzni. Így csak a CC DD és

a CD DD stratégia marad. Az egyszer¶sített élettartam mátrixot az 5.3. táblázat mutatja. 5.3. táblázat. Tranzienseket gyelembe vev® élettartamok 2 3 B 3

2 3

B R

;

B 3

+ ²1 ;

B R B R

B R

;

B R

+ ²2 ;

+ ²1 B R

+ ²2

Ez a táblázat már gyelembe veszi a tranziens lépéseket is. A tranziens lépések abból következnek, hogy a szenzorok teljesen sikeres el®élettel kezdik el a m¶ködésüket, ezen kívül a haláluk sem feltétlenül ciklus végén következik be, ezért az élettartamuk végén lév® csonka ciklus is tranziens lépéseket okoz. A ciklikusság abból ered, hogy a lehetséges lépések véges száma miatt a szenzorok egy id® után mindenképpen egy olyan állapotba jutnak, ami egyszer már el®fordult. Innen kezd®dik az újabb ciklus. A ciklus hossza jellemz®en egyezik az ablak hosszával. A tranziens lépések számát nem könny¶ meghatározni, de könny¶ felülr®l becsülni. Jó fels® becslés lehet a ciklus (ablak) hossza, mert ha nagyobb lenne, akkor a ciklusok száma n®ne eggyel. Mivel általános esetben az élettartam nagyságrendileg nagyobb, mint a ciklus (ablak) hossza, ezért általában el lehet hanyagolni a tranziens lépéseket vagy legalábbis az nem változtatja meg az eredményeket. Az 5.3. táblázatban a tranziens lépések hatását az ²i -k jelölik. Az 5.3. táblázatból már látszik, hogy két Nash-egyensúlya van a rendszernek. Ezek a CC DD - CC DD és a CD DD - CD DD párosítások. Az el®bbi mindkét félnek kedvez®bb, mivel itt mindkét fél hosszabb életet tud elérni, ha teljesül a következ® feltétel:

3

1 3

esetén,

ami jellemz®en teljesül. Ebb®l következ®en ebben az egyszer¶ esetben kialakul a teljes kooperáció minden küls® serkentés nélkül.


58

5.2. Az utolsó lépés modell A kétlépéses stratégiák vizsgálati ereményei tehát bíztatóak volt, érdemesnek láttam b®víteni a vizsgált stratégiák terét. Vigyázni kellett azonban a b®vítés mértékével. Egy példával szemléltetve: ha B = 120, w = 10 és ρ = 0,9, akkor a rendszer rövid ideig fog élni a magas elvárt sikerráta miatt, de még így is 2L -en stratégia lehetséges (ρ magas értéke miatt mindig defektálni kell, innen a 2-es alap), ahol L =

B 2α +2

határesetben. α értékét az

analítikus vizsgálatok során 2-nek választottam, ezzel az értékkel számolva L-re 20 adódik. Vagyis az összes stratégiák száma 22 0, ami nem t¶nik soknak, viszont ha belegondolunk, hogy a legjobb stratégia megtalálásához az összes lehetséges stratégiapárt mérk®ztetni kell, akkor azt kapjuk, hogy ennél a lebutított esetnél is majd 9 évig számolna a számítógép, ha másodpercenként 1000 párral végezne. Látható tehát, hogy a modell b®vítésének az általánosság minél jobbani megközelítése mellett praktikus okok szabtak határt. Ezért a b®vítést lépésr®l-lépésre végeztem el, de a legfontosabb az, hogy olyan modelleket alkalmaztam, melyek logikus kiterjesztései a korábbiaknak. A kétlépéses stratégiák jelent®s kib®vítése a következ® stratégiatér. A stratégiák a saját utolsó lépésüket, és annak sikerességét veszik gyelembe a következ® lépés meghatározásánál. Ez már egy egyértelm¶ és közvetlen visszacsatolás a játékos felé, amivel látszólag jól és hatékonyan lehet szabályozni a stratégiát. Ebben a stratégiatérben minden stratégiát 13 bittel lehet reprezentálni. Egy biten lehet ábrázolni, hogy kényszerhelyzetben a DC és DD közül melyik biztos lépést választja a stratégia. Ha nincs kényszerhelyzet, akkor mindig négyféle lépése lehet a stratégiának (CC, CD, DC, DD), úgyhogy ezeket az eseteket két-két bittel lehet leírni. Összesen hat különböz® helyzet fordulhat el®:

• utolsó lépés CC volt, és sikeres volt az adás • utolsó lépés CC volt, és sikertelen volt az adás • utolsó lépés CD volt, és sikeres volt az adás • utolsó lépés CD volt, és sikertelen volt az adás • utolsó lépés DC volt, ez mindig sikert eredményez • utolsó lépés DD volt, ez mindig sikert eredményez


59

Ez összesen 1 + 2 · 6 = 13 bit. Ez azt jelenti, hogy a stratégiatérben 213 = 8192 stratégia található. Kényszerhelyzetben azért x a stratégia, mert ezzel jelent®sen lehetett csökkenteni a szóbajöv® stratégiák számát. Egy lehetséges b®vítése a stratégiatérnek, ha nem x a stratégia kényszerhelyzetben, hanem az is az el®z® lépést®l, és annak sikerességét®l függ, bár nem valószín¶, hogy ez jelent®sen befolyásolná az eredményeket. Az 5.2. ábrán egy példa stratégia látható. Ez nem feltétlenül egy okos stratégia, csak a stratégiák ábrázolását szemlélteti. A stratégia kényszerhelyzetben mindig DD-t játszik (1. bit). Ha az utolsó lépés CC és sikeres volt, akkor DC-t (2. és 3. bit), ha sikertelen, akkor DD-t (4. és 5. bit) játszik. Ha az utolsó lépés CD és sikeres volt, akkor DC-t (6. és 7. bit), ha sikertelen volt, akkor CC-t (8. és 9. bit) játszik. Ha az utolsó lépés DC volt, akkor DD-t (10. és 11. bit) játszik, ha az utolsó lépés DD volt, akkor DC-t (12. és 13. bit) játszik.

stratégia

1 1 0 1 1 1 0 0 0 1 1 1 0

bitsorszám

1.

2. 3.

4. 5.

6. 7.

8. 9. 10. 11. 12. 13.

5.2. ábra. Példa stratégia az utolsó lépés modellhez

Az utolsó lépéses stratégiateret már szimulációval vizsgáltam. A szimulációhoz a Matlab matematikai programnyelvet használtam. El®ször el®állítottam az összes élettartamot tartalmazó mátrixot adott paraméterek mellett. Ez egy 8192-szer 8192-es mátrix, amiben az Mi,j mez® az i. és a j . stratégia párosításával elérhet® élettartamokat mutatja.

5.2.1. Az utolsó lépés modell vizsgálati eredményei Az el®z® modellnél már leírt módon kiválogattam a maximális Nash-egyensúlyokat. Ezek az egyensúlyok

B B ; 3 3

ideig élnek. Ez azt mutatja, hogy racionális viselkedés esetén mindig

kialakul a teljes kooperáció. Egy jó példa az optimális stratégiákra a 4096-os stratégia (5.3. ábra). Ez a kétlépéses stratégiák közül a szigorú stratégiát valósítja meg, ami a legjobb stratégia volt az egyszer¶ stratégiák között. Az ábrán a folytonos nyíl a normál átlépést jelenti az állapotok között, a szaggatott nyíl a kényszerhelyzetben tett lépést. A stratégia CC-vel kezdi el az életét, és mindig CC-t játszik, míg nem kerül a sikerességi rátája veszélybe. Ekkor DD-t játszik,


60

CC

CD

DC DD

5.3. ábra. A 4096-os stratégia amíg el nem múlik a veszély, ezután újra CC-t játszik. Ha mindkét játékos ezt a stratégiát játsza, akkor az egy olyan Nash-egyensúlyt valósít meg, aminél nem lehet jobbat elérni ( B3 ; B ) 3

ebben a stratégiatérben. A stratégia jól láthatóan nem használja ki a visszacsatolásokat. A lépések nem függenek

sem az utolsó lépést®l, sem annak sikerességét®l. A stratégia egyedül a sikerességi rátáját gyeli, amire már az egyszer¶ stratégiák is képesek voltak. Tehát levonható a következtetés, hogy a stratégiatér ilyen irányú kib®vítése nem hoz jelent®s eredményeket.

5.3. A vektorsúlyos modell Az utolsó lépés modell láthatóan nem elégítette ki kívánalmainkat, ezért egy már bonyolultabb, a játékos számára sokkal nagyobb szabadságot adó modellt dolgoztam ki. Ezt vektorsúlyos modellnek neveztem. E modell esetében egy w − 1 hosszúságú vektorban tároljuk az utolsó w − 1 lépés eredményét. A játékosok minden lépés el®tt végignézik ezt a vektort és összeszámolják, hogy hány sikeres lépésük volt (kiszámolják a vektor súlyát). Amennyiben a sikerességi rátájuk (s) megengedi, hogy egy esetleges sikertelen lépésre vállalkozzanak, úgy a négy lehetséges lépés közül bármelyiket választhatják. Ha a sikeresség


61

mértéke a megadott szint (ρ) alá csökkenne egy sikertelen lépéssel, akkor csak a DC és a DD lépések közül választhatnak. Egy-egy stratégia tehát s lehetséges értékeinek megfelel® lépések sora, pl. w = 5-re és ρ = 0,4-re egy lehetséges stratégia a DC CC DD (vagyis

s = 0,8-ra DC a kívánt lépés, s = 0,6-ra CC és a kritikus s = 0,4-re DD több eset nincs). Miután megszületett a döntés, végrehajtódik a lépés és az eredménye bekerül az el®élet-vektorba. A játék addig tart, amíg a szenzorok fel nem élik a büdzséjüket. Mivel a különböz® lépések különböz® mennyiség¶ energiát igényelnek (különböz®képpen terhelik a szenzorok büdzséjét), érdemes minden pillanatban az optimális lépést választani. A kérdés az, hogy melyik ez a lépés! A válasz nem is olyan egyszer¶. Tegyük fel, hogy úgy állítjuk be a szenzorainkat, hogy azok végig defektáljanak (akár ebben a modellben, akár általános esetben). Ezzel azt érnénk el, hogy ugyan a sikerességünk kritikán felüli lenne (ami mellesleg nem cél), viszont id® el®tt lemerülnének az eszközeink az energiaigényes kommunikáció miatt. Ez tehát láthatóan nem jó. Nézzük a másik végletet, amikor is a szenzorok végig kooperálnak, vagyis CC-znek. Ekkor úgy t¶nik, hogy mindenki jól jár, hiszen ha a másik szenzorhálózat Tit-for-Tat jelleg¶ alapbeállításokkal bír, akkor viszonozni fogja a mi kooperatív viselkedésünket és szintén CC-zni fog. A sikerességünk megint tökéletes lenne, viszont jelent®sen n®ne az élettartamunk, vagyis már most hatalmasat léptünk a cél felé, ami ugyebár az élettartam maximalizálása. Igenám, de továbbra sem cél a makulátlan sikeresség. Nem lehetne valahogy úgy játszani, hogy a sikerességünkb®l kicsit alábbhagyva meghosszabbítsuk az élettartamunkat?

5.3.1. A vektorsúlyos modell vizsgálati eredményei A vektorsúlyos modell eredményeinek megértéséhez érdemes egy új rendszerparamétert származtatni, a szabadságfokot (η ). A rendszer szabadságfoka egy mértékegység nélküli szám, amely azt adja meg, hogy az adott rendszerparaméterek mellett hány olyan lehetséges

s (sikerességi ráta) érték van, amikor megkötések nélkül választhatunk következ® lépést. Értelemszer¶en η = b(1 − ρ)wc − 1. A szabadságfok jelent®sen befolyásolja egy rendszer komplexitását, hiszen nagyobb szabadságfokokra exponenciálisan több stratégia létezik. η ismeretében most már könnyen megadható a lehetséges stratégiák halmazának számossága is: kSk = 4η · 2, ahol S a stratégiahalmaz.


62

Ezután már interpretálhatóak az eredmények, melyeket változó ablakméretek (w) és elvárt sikerráta (ρ), de állandó büdzsé (B = 200) mellett mértem.

0 szabadságfokú rendszerek esetében a szenzoroknak nincs módjuk kooperálni, mivel az elvárt sikerráta olyan nagy, hogy mindig biztosra kell menniük, vagyis csak D* lépésekkel m¶ködhetnek. Még ha az egyik játékos DC lépést választ is, segít®készségének nem lesz értelme, hiszen a másik játékos nem vállalhat el egyetlen rizikós C* lépést sem. Sajnos itt nem igazán beszélhetünk játékról, hiszen nincs meg az a szabadság (szabadságfok), amivel az igazi játék kialakulhatna. Ily módon ez az eset csak a teljesség kedvéért szerepel a felsorolásban.

1 szabadságfokú rendszerek esetén már kialakul a kooperáció egy kezdetleges formája! Mindkét félnek az a legjobb, ha meg sem próbál defektálni, mivel az esetleg rögtön azt eredményezné, hogy a következ® lépésben visszakapja a kapitulálást és ezáltal a jóval drágább D* lépést lesz kénytelen választani. Mivel a játék egyel®re teljesen szimmetrikus, mindkét fél CC-zéssel fog kezdeni és mindvégig meg is marad ennél a lépésnél. Mivel a CC-zés költsége 3, ezért az élettartam

B 3

mindig.

2 szabadságfokú rendszerek esetében már kezd érdekessé válni a kép: megjelenik egy bizakodó lépés (CD), vagyis mindkét fél el®ször fölméri, hogy ki lehet-e használni a másikat, majd ha ez nem sikerül, akkor barátságossá válik (CC-zik). Fontos látni, hogy ezek a maximális Nashegyensúlyi stratégiák csak addig próbálkoznak egy esetleg sikertelen lépéssel, amíg még a sikerességi ráta a kritikus szint (ρ) fölött tartható defektáló (D*) lépések nélkül is. Soha nem fordul el®, hogy hosszan kellene adniuk, mivel még miel®tt kényessé válna a helyzet, bedobnak egy barátságos CC lépést, amivel a szimmetria miatt garantálni tudják a sikerességi rátájuk inkrementálódását. Ebben az esetben a szenzorhálózatok élettartama már függ az aktuális ablakmérett®l, mert megjelenik az említett CD lépés, amivel mintegy feltérképezik a játékosok a szituációt. Az ablak méretével fordítottan arányos az elérhet® maximális élettartam, hiszen minél hosszabb az ablak, annál több ideig tart, amíg egy-egy sikertelenség (0-ás bejegyzés) ki tud shiftel®dni bel®le és amíg nem érdemes újra egy CD lépéssel próbálkozni.

3 szabadságfokú rendszerek vizsgálatakor azt kapjuk, hogy az el®z® eset analógiájára viselkednek a felek. Ez azonban egy fontos vizsgálati lépés, hiszen ett®l a ponttól válik


63

valószín¶vé, hogy a nyer® stratégiák valamilyen egyszer¶, szabadságfok-függ® leképezést követnek. Az optimális stratégiák mindössze annyival b®vültek a két szabadságfokú rendszerekhez képest, hogy bekerült egy újabb CD lépés a sorba. Vagyis most a felek többször is megpróbálják kihasználni egymást, de csak addig, ameddig még nem válik kritikussá a helyzet és még azel®tt barátságossá válnak, miel®tt esetleg belekényszerülnének egy hosszú adásba. Érdekesség, hogy most a kis ablakméret még nem garancia a sikerre, mert w = 5 esetén a kapott élettartamok alulmúlják a hosszabb ablaknál kapott értékeket. Ennek feltételezhet®en az az oka, hogy w = 5-nél a 3 szabadságfokot úgy tudjuk elérni, hogy ρ-t 0,2-re állítjuk. Ez azt jelenti, hogy

ρ<

1 , 2α −1

amikor is már más stratégia számít jónak, ahogy azt az el®z®ekben láthat-

tuk. A probléma azonban nem komoly, hiszen a valóságban nem valószín¶, hogy ilyen alacsony sikerrátát kellene beállítanunk egy szenzor kongurálásánál. Az eredmények úgy t¶nik koherensek lettek egymással és egyben megfelelnek az elvártaknak. Azt kaptuk, hogy létezik ideális stratégia, amennyiben az élettartam maximalizálása a cél. Az elvárásoknak megfelel® stratégia számító, hiszen mindig megpróbál a másikon él®sködni, de ha látja, hogy ez nem fog menni, akkor még azel®tt változtat a szokásain, miel®tt kritikussá válna a helyzet. Nem fordul el® az, hogy a drága hosszú adás (D*) mellett kelljen dönteniük a feleknek (kivéve a η = 0 esetet, amit igazából nem érdemes vizsgálni) és így tudják biztosítani maguknak a hosszabb élettartamot. A kezdeti CD lépések biztosítják a minimális energia-felhasználást, így lehetséges, hogy az élettartamok általában a naív kooperáció esetére adódó

B 3

fölött vannak. Az általános alakban felírt

ideális stratégia tehát a következ®:

[CD]η−1 CC D∗ Ez az általános stratégia tehát az els® η − 1 lépésben CD-zést ír el®, majd egy CC lépést, befejezésképpen pedig egy D* lépést, ami lehet DC vagy DD is tetszés szerint. Végül elmondható, hogy a kapott kifejezés kooperatív stratégiát ír le, vagyis a vektorsúlyos modell alapján m¶köd® rendszerekben minden egyéb ösztönz® hatás nélkül kialakul a kooperáció.

6. fejezet A b®vített modell Az eddigi modellekben mindig az 5.1. ábra által szemléltetett elrendezést vizsgáltam. A kétlépéses stratégiák tere már bizonyítottan kicsi volt komolyabb vizsgálatok elvégzéséhez, míg az utolsó lépés modell alulmaradt a vektorsúlyos modellel szemben, ami a játékosok élettartamát illeti ugyanazon elrendezés mellett. Ennek az oka a már említett visszacsatolás volt, pontosabban az, hogy a vektorsúlyos modell valóban felhasználja a visszacsatolással kapott információt, míg az utolsó lépés modell nem. Vizsgálataimat tehát ezentúl a vektorsúlyos modellel folytattam. A kezdeti kis modellt kiterjesztettem el®ször is egy dimenzióra, vagyis egy bázisállomást feltételezve a szenzorokat egy vonalban raktam le. Egyaránt vizsgáltam a szimmetrikus és a nem szimmetrikus eseteket. Szimmetrikus elrendezésen azt értem, amikor a bázisállomás mindkét oldalán vannak szenzorok és minden fekete szenzornak megfeleltethet® egy fehér, amelyik vele azonos távolságban van a bázistól. Az egyszer¶sített modell szimmetrikus elrendezés¶nek számít. Aszimmetrikus elhelyezésr®l akkor beszélünk, ha a fenti kritérium nem teljesül. A b®vített modellben már fontos kérdéssé vált az útválasztás problémája, aminek algoritmusáról a 3.1.1. alfejezetben írtam. Az eredeti vektorsúlyos modellt több rendszerparaméter függvényében vizsgáltam. Ezek a visszacsatolási vektor hossza, az elvárt

sikerráta és a szenzorok büdzséje. A dimenziób®vítés más vizsgálati szempontokat igényelt. A visszacsatolási vektor hossza és a szenzorok büdzséje a további vizsgálatok során végig ugyanazokat az értékeket vette fel, persze a szimulátorban változtatható paraméterként szerepelnek. Az elvárt sikerráta értéke is konstans lett. Azáltal, hogy két-két szenzor helyett a továbbiakban több szenzorral fogunk dolgozni, be kellett vezetni az életbenmaradási

indexet. Ez egy 0 és 1 közé es® valós szám, ami azt adja meg, hogy a szenzorok közül 64

6. FEJEZET. A BVÍTETT MODELL

65

arányait tekintve hány darabnak kell minimálisan életben lennie ahhoz, hogy a meghatározott mérési feladatot teljesíteni tudják. Ha az él® szenzorok száma a kezdeti szenzorszám és az életbenmaradási index szorzata alá süllyed, akkor az egész adott szín¶ hálózat kikapcsol. Megjegyzend®, hogy már az egyszer¶sített modellben is szerepelt egy implicit életbenmaradási index, hiszen annak érdekében, hogy a kooperáció egyáltalán el®fordulhasson, megköveteltem, hogy egy játékos mindkét szenzora életben legyen (vagyis az életbenmaradási indexet 1-re állítottam). Szintén új paraméter az id®intervallumokban értelmezett teljesítmény index. Ez egy 0 és 1 közé es® arányszám, amely egy adott id®intevallum sikeresnek dedikálásához szükséges beérkezett csomagszám arányt határozza meg. Vagyis, amennyiben a bázishoz egy intervallumban ennél kisebb arányban érkeznek csomagok, úgy az az intervallum sikertelen (a sikervektorba egy 0-ás bejegyzés kerül), egyébként sikeres (a sikervektorba egy 1-es kerül). A teljesítmény indexr®l is elmondható, hogy implicite része volt az egyszer¶sített modellnek is 1 értékkel. Változóvá vált továbbá a bázisok száma és azok elhelyezkedése is. A bázisok száma két értéket vehet fel: lehet 1 és lehet 5. Amennyiben egy bázist feltételezünk, úgy az a játéktér közepén található, ha öt bázist feltételezünk, akkor azok elhelyezkedése az egyenletes eloszlást követ®en véletlenszer¶. A továbbiakban ezért a több bázist szimuláló esetekben a bázisok elhelyezkedésére nem térek külön ki, csak azok számára. Természetesen változó paraméterré vált a modellben a szenzorok száma, valamint azok

elhelyezkedése is. Emiatt már nem mérvadóak az 5.1. táblázatban leírt költségek, viszont annak analógiájára a következ® változásokat vezettem be a költségszámolás terén. A szenzorok csomagküldési költsége mindig a szenzor és a címzett közötti távolság függvénye a 2.1. fejezetben leírtaknak megfelel®en. Ha egy szenzor saját csomagot is küld és másoknak is segít, akkor a szenzor költsége az egyes csomagok költségeinek összege. A továbbiakban tehát ezen öt paraméter (életbenmaradási index, teljesítmény index, bázisok száma, szenzorok száma, szenzorok elhelyezkedése) függvényében vizsgáltam a kib®vített vektorsúlyos modellt.

6.1. Vizsgálati eredmények egy bázis esetére Ebben a fejezetben végig egyetlen bázist feltételeztem a tér közepén elhelyezve. Minden szenzor ennek a bázisnak továbbítja a mérési eredményeit.


66

100

90

80

70

60

50

40

30

20

10

0

0

10

20

30

40

50

60

70

80

90

100

6.1. ábra. Egydimenziós szimmetrikus hálózat

6.1.1. Szimmetrikus esetek El®ször a legegyszer¶bb eseteket vizsgáltam, nevezetesen az egydimenziós szimmetrikus eloszlásokat. Ilyen topológiára példa a 6.1. ábra. A kék és a piros pontok felelnek meg a különböz® szervezetek irányítása alatt álló szenzoroknak, míg a kék négyzet a bázisállomást jelképezi. Ezekben a hálózatokban mindig és kizárólag a CD CC D* stratégia nyert. A legtöbb esetben megjelent a gy®ztesek között mindkét verziója (CD CC DC és CD CC DD), de a CD CC DD mindig nyert. Ez a stratégia egy óvatos felderítés után kooperatívan játszik mindig, ha a sajátjával megegyez® stratégiával találkozik. Tehát levonható a következtetés, hogy az egydimenziós szimmetrikus elhelyezkedés esetén kialakul a kooperáció. A vizsgálatokat kétdimenziós szimmetrikus modellekkel folytattam. Mivel ez a hálózat (6.2. ábra) tulajdonképpen két keresztben elhelyezett egydimenziós hálózatnak felel meg, ezért nem meglep® módon hasonló eredmények születtek, mint az egydimenziós esetben. Tehát itt is mindig a CD CC D* stratégiák nyertek. A vizsgálatokat sokkal érdekesebb hálózatokkal folytattam, ezek a véletlen elhelyezkedés¶ hálózatok. A véletlen elhelyezkedés sokkal reálisabb, mint a szimmetrikus elhelyezkedés, ezért ezek után nem is hagytam el a véletlen hálózatok világát. A véletlen hálózatok vizsgálatát is egydimenzióban kezdtem el. Az ilyen hálózatok el®fordulása nem valószín¶,


67

100

90

80

70

60

50

40

30

20

10

0

0

10

20

30

40

50

60

70

80

90

100

6.2. ábra. Kétdimenziós szimmetrikus hálózat

inkább a szimulátor ellen®rzése miatt próbáltam ki ezt az egyszer¶bb felállást. Az eredmények sokkal változatosabbak lettek, mint a szimmetrikus esetekben. 6.1. táblázat. Egydimenziós véletlen szimulációk ÉI ; TI Kooperatív [%] Nem kooperatív [%] Élettartamok átlaga 0.6 ; 0.6

50

50

311.3

0.8 ; 0.8

83

17

231.5

0.9 ; 0.9

40

60

146.2

A szimuláció kimenetei a 6.1. táblázatban találhatók. A táblázat els® oszlopa a paramétereket tartalmazza: életbenmaradási index (szenzorok mekkora arányának kell életben lennie, hogy a hálózatot m¶köd®nek tekinthessük); teljesítmény index (a szenzorok mekkora arányának kell a csomagját célba juttatni, hogy a kört sikeresnek tekinthessük). A második és harmadik oszlop a nyertes kooperatív és nem kooperatív stratégiák arányát tartalmazza. Kooperatív stratégiának számít most az a stratégia, amelyikben van legalább egy segít®kész lépés még a kényszerhelyzet el®tt (*C ** D* vagy ** *C D*). Nem kooperatív stratégia az, amelyikre ez a deníció nem illik.


68

A táblázatból jól látszik, hogy gyakran kialakul kooperáció, de nem kizárólagos, s®t szigorú feltételek mellett (utolsó sor) jellemz®bb a nem kooperatív viselkedés. Ez érthet® is, hiszen ilyen szigorú feltételek mellett kis hiba esetén is veszélybe kerülhetnek a feltételek. Így jellemz®en érdemes kockázatkerül® stratégiát választani. A táblázatból kiolvasható, hogy a szigorúbb feltételek rövidebb élettartamot eredményeznek, de ez következik már a modellb®l is.

6.1.2. Aszimmetrikus esetek Ezek az inkább a szimulátor ellen®rzését célzó szimulációk után következtek a valósághoz közelebb álló modellek, a kétdimenziós véletlen elhelyezkedés¶ szimulációk. Ezeket különböz® paraméterekkel futtattam, különböz® szenzors¶r¶ségek mellett. A 6.2. táblázat a kétszer tíz szenzorból álló hálózat szimulációs eredményeit tartalmazza. 6.2. táblázat. Kétdimenziós véletlen szimulációk, 10+10 csomópont ÉI ; TI Kooperatív [%] Nem kooperatív [%] Élettartamok átlaga 0.6 ; 0.6

61

39

110.6

0.8 ; 0.8

50

50

63.4

0.9 ; 0.9

56

44

49

A táblázatból látszik, hogy minden esetben legalább annyira érdemes kooperatív stratégiát választani, mint nem kooperatívat. A kooperatív stratégiák közül minden esetben a CD CC DD stratégia nyert kimagaslóan, tehát ha csak egy stratégiát lehet a szenzorokba programozni, akkor ezt a legcélszer¶bb. A 6.3. táblázat a kétszer húsz szenzorból álló hálózat szimulációs eredményeit tartalmazza. Ebben a hálózatban a s¶r¶ség kétszer akkora, mint a kétszer tíz szenzort tartalmazó hálózatban. Ennek következtében az átlagos élettartamok n®nek, illetve egyre könnyebb egy-egy adatcsomagot a bázishoz csak a saját hálózatot használva eljuttatni. Ebb®l kifolyólag a kooperáció szükségessége csökken, ami meg is jelenik az eredményekben. Ezek után a tendenciát ellen®rizend® tovább növeltem a szenzorok számát ötvenre (6.4. táblázat). A szimulációs eredmények igazolták a sejtést, a nagy s¶r¶ség a kooperáció ellen dolgozik. A s¶r¶ség extrém mivoltának érzékeltetésére szolgál a 6.3. ábra.


69

6.3. táblázat. Kétdimenziós véletlen szimulációk, 20+20 csomópont ÉI ; TI Kooperatív [%] Nem kooperatív [%] Élettartamok átlaga 0.6 ; 0.6

47

53

150.6

0.8 ; 0.8

35

65

88.2

0.9 ; 0.9

53

47

59.8

6.4. táblázat. Kétdimenziós véletlen szimulációk, 50+50 csomópont ÉI ; TI Kooperatív [%] Nem kooperatív [%] Élettartamok átlaga 0.8 ; 0.8

19

81

98.9

0.9 ; 0.9

45

55

76.7

100

90

80

70

60

50

40

30

20

10

0

0

10

20

30

40

50

60

70

80

90

100

6.3. ábra. Kétdimenziós véletlen hálózat, 50+50 csomópont

Tehát levonható a következtetés, hogy egy közös bázisállomás esetén csak akkor érdemes kooperatív stratégiát választani, ha nem túl s¶r¶ a hálózat.


70

6.2. Vizsgálati eredmények több bázis esetére A szimulációkat sorát több közös bázisállomással folytattam. Itt már nem vizsgáltam a szimmetrikus elrendezéseket, hiszen eleve már a bázisállomások is véletlenszer¶en kerülnek lehelyezésre, azonkívül az ilyen esetek a gyakorlatban csak elvétve fordulhatnak el®. A több bázisállomás feltételezése jelent®s lépés a valóságos hálózatok felé, hiszen könny¶ elképzelni olyan helyzetet, ahol egy szervezet telepíti a bázisállomásokat, és más szervezetek telepítik a különböz® érzékel®ket. Ilyen helyzet el®fordulhat például egy repül®téren, a kórházakban vagy a közigazgatás bármely területén. A szimulációkat egy ritkább hálózattal kezdtem, ami kétszer tíz szenzorból és öt közös bázisállomásból állt (6.5. táblázat). Az eredményekb®l jól látszik, hogy a kooperációt jelen esetben a szigorúbb feltételek, a magasabb életbenmaradási index és a magasabb teljesítmény index fokozzák. Ugyanezen szigorúbb feltételek természetesen csökkentik az átlagos túlélési id®t. 6.5. táblázat. Kétdimenziós véletlen szimulációk, 10+10 csomópont, 5 bázis ÉI ; TI Kooperatív [%] Nem kooperatív [%] Élettartamok átlaga 0.6 ; 0.6

39

61

196.5

0.8 ; 0.8

43

57

127.4

0.9 ; 0.9

52

48

108.6

6.6. táblázat. Kétdimenziós véletlen szimulációk, 20+20 csomópont, 5 bázis ÉI ; TI Kooperatív [%] Nem kooperatív [%] Élettartamok átlaga 0.6 ; 0.6

25

75

209

0.8 ; 0.8

30

70

124.5

0.9 ; 0.9

23

77

95.5

A szimulációkat egy s¶r¶bb hálózattal folytattam, ami kétszer húsz szenzorból és továbbra is öt bázisállomásból állt. Az eredményeket a 6.6. táblázat tartalmazza. Ilyen szenzors¶r¶ség mellett a feltételek szigorítása el®bb segíti a kooperáció kialakulását, majd gátolja azt. Ez azért van így, mert a kooperációban mindig van valamilyen kockázat, és nagyon szigorú feltételek mellett csak ritkán lehet tolerálni ezt a kockázatot.


71

A két táblázat összehasonlításából látszik, hogy az egybázisos esethez hasonlóan a nagyobb s¶r¶ség a kooperáció ellen hat. Ez azt jelenti, hogy a szenzorokat telepít® szervezeteknek ajánlatos inkább kevesebb szenzort telepíteni és kooperatívan játszani, mert ezzel amellett, hogy n® a hálózat élettartama, még annak fenntartási költsége is csökken a kisebb szenzorszám miatt.

7. fejezet A b®vített modell továbbfejlesztése A b®vített modell vizsgálata során kapott eredmények ugyan megfelelnek az elvárásainknak és viszonylag szépen körvonalazzák a változók értékeinek azon tartományát, amelyek mellett érdemes a szenzorokat kooperatív viselkedésre programozni, ugyanakkor az élettartamok relatív szórásának tapasztalt mértéke kétségeket ébresztett, hogy vajon ez a kooperatívnem kooperatív besorolás nem túlságosan leegyszer¶sített-e. Érdemesnek láttam tehát a modellt újra átgondolni és bizonyos pontokon továbbfejleszteni. Els®sorban az eredmények kiértékelésének módján változtattam, de maga a szimulátor is átalakult. A szimulátor legfontosabb újdonsága, hogy megjelent benne a vételi x költség és az

adási x költség fogalma. Az utóbbi néhány hónap nemzetközi kutatásai rávilágítottak, hogy a szenzorok kommunikációjában nem csak a távolságtól és az α-tól függ az elhasznált energia mennyisége, hanem ahhoz még additívan csatolódik a vételi- ill. adási x költség, attól függ®en, hogy az aktuálisan tekintett szenzor épp csomagot fogad vagy csomagot küld ([7, 24]). A x költségek a szenzor rádiójának be- ill. kikapcsolását, a csatornához csatlakozást és az adatcsomagon elvégzett m¶veletek energiaigényét hivatottak reprezentálni. A program másik nagy változását az életbenmaradási index elhagyása jelentette. Eddig két kritériumunk volt: az életbenmaradási index, amely a minimálisan életben lév® szenzorok arányát határozta meg, valamint a teljesítmény index, ami a bázis által megkövetelt minimális csomagszámot adta meg. Látható, hogy ez a két kritérium összevonható, hiszen ha egy bizonyos százaléknál kevesebb szenzor él, akkor azok úgysem tudják teljesíteni a minimális csomagszám követelményét. A modell kézbentarthatósága érdekében tehát a további vizsgálatok folyamán eltekintettem az életbenmaradási indext®l. A szimulátor által szolgáltatott eredmények kiértékelése a következ® változásokon esett 72

7. FEJEZET. A BVÍTETT MODELL TOVÁBBFEJLESZTÉSE

73

át. Eddig és ezután is stratégiapárokkal kapcsolatban beszélhettünk élettartamokról, hiszen a szimulátor a stratégiákat egymással mérk®ztetve határozza meg az azokhoz tartozó élettartamokat. A kooperatív ill. a nem kooperatív viselkedést viszont stratégiákra mondtam ki, vagyis mintegy szétválasztottam a stratégiapárokat alkotó stratégiákat. Ez a naív szemlélet sok szempontból megfelel®, viszont esetleg torz képet adhat a játékosok viselkedését tekintve. Ezért úgy döntöttem, hogy a továbbfejlesztett modellben már nem a stratégiákat fogom osztályozni, hanem a stratégiapárokat. Egyszer¶ megközelítésnek t¶nik, hogy az eddig a stratégiákra alkalmazott csoportosítást terjesszük ki a stratégiapárokra, vagyis például egy stratégiapár akkor legyen kooperatív, ha mindkét stratégiája az. Sajnos felmerül egy probléma ezzel az megközelítéssel kapcsolatban. Képzeljük el azt az esetet, hogy a stratégiapárunk mindkét stratégiája kooperatív, mégis az egyik fél kihasználja a másikat. Egy ilyen pár például a CC CC DC - CD CC DC, hiszen a második játékos stratégiája ugyan kooperatívnak számít a CC lépés miatt, viszont mivel az els® játékos minden csomagot továbbít, a második játékos soha nem fog mást lépni, mint CD-t (csak a játék végén, mikor az els® játékos már meghalt). Ugyanígy, mivel a második játékos végig CD-t lép, az els® játékos csomagjait soha nem továbbítja. Abból a felismerésb®l, hogy a stratégiákat nem elég egyszer¶en csak a formájuk után osztályozni, született meg a gondolat, hogy azok játék közbeni viselkedését kellene alapul venni a kategorizálásnál. A szimulátort kib®vítettem tehát egy-egy csomagszámlálóval, ami azokat a csomagokat regisztrálja mindkét játékos oldalán, amelyek továbbításához valóban segítséget kaptak a felek, vagyis ahol ténylegesen megjelent a kooperáció. A maximális Nash-egyensúlyi stratégiapárokra kapott számadatokat ezután három diszjunkt kategóriába soroltam:

0. kategória Egyik fél sem továbbít egyetlen csomagot sem kooperatív módon (nincs kooperáció).

1. kategória Csak az egyik fél segíti a másikat a csomagtovábbítással, a segítség nem kölcsönös (fél-kooperáció).

2. kategória Mindkét fél kölcsönösen segíti egymást, vagyis legalább egy csomag kooperatív módon továbbítódott a bázis felé mindkét játékos részér®l (teljes kooperáció). A továbbiakban ennek a kategorizálásnak megfelel®en fogom az eredményeket bemutatni, amik már a továbbfejlesztett szimulátor segítségével készültek.


74

Megjegyzend®, hogy az eddigi eredményeim, amiket még a régi kooperáció-fogalom alapján prezentáltam, nem hibásak. Szimulációval megmutattam, hogy valóban kooperatív stratégiákat érdemes a szenzorokba programozni, mert azzal fogják a szenzorhálózatok a leghosszabb élettartamot elérni. A cél pedig ez volt. Ez utóbbi megközelítés a kooperáció fogalmának egy másik megközelítése, ami talán tisztább képet ad a szenzorhálózatok, mint dinamikus rendszerek m¶ködésér®l, bels® folyamatairól.

7.1. A továbbfejlesztett modell vizsgálati eredményei A továbbfejlesztett szimulátor futási paramétereinek értékeit a 7.1. táblázat tartalmazza. A zárójelben feltüntetett értékek az alapértelmezettek, a különböz® futásoknál csak egy változó értékét módosítottam, a többi az alapértelmezett értéket vette fel. 7.1. táblázat. Szimulációs paraméterek a továbbfejlesztett modellhez

Paraméter

Érték

Játékosonkénti szenzorszám

10-20-40 (20)

Kezdeti akkumulátor

10 millió egység

Fogadási x költség

3000 egység

Küldési x költség

2000 egység

Teljesítmény index

0,7-0,8-0,9 (0,8)

Energiafogyasztási tényez® (α)

2-3-4 (3)

Szimulációk száma

100

Az eredményeket a 7.1., a 7.2. és a 7.3. ábrák mutatják. Az x tengelyen az ismertetett kooperációs kategóriák szerepelnek, az y tengelyen a stratégiapárok százalékos eloszlása. A grakon oszlopait a maximális Nash-egyensúlyi stratégiapárok adják. Egy adott futás eredményét az abban megjelen® legmagasabb kooperációs szint szerinti kategóriába soroltam. A 7.1. ábrán látszik, hogy az esetek többségében kialakul valamiféle kooperáció. A ritkább hálózatokban nagyobb eséllyel jön létre a teljes kooperáció, mint a s¶r¶bbekben, aminek feltételezhet®en az az oka, hogy a s¶r¶bb hálózatokban már a játékosoknak egyedül is van annyi szenzoruk, amivel költséghatékonyan tudnak csomagot továbbítani, kevésbe


75

100

10 szenzor / játékos 20 szenzor / játékos 40 szenzor / játékos

90

80

Eloszlás [%]

70

60

50

40

30

20

10

0

0

1

2

Kooperációs kategóriák

7.1. ábra. Stratégiapárok kooperációs kategóriák közötti megoszlása a szenzorok számának függvényében 100

90 alfa = 2 alfa = 3 alfa = 4

80

Eloszlás [%]

70

60

50

40

30

20

10

0

0

1

2


7.2. ábra. Stratégiapárok kooperációs kategóriák közötti megoszlása az energiafogyasztási tényez® (α) függvényében

kell igénybe venniük a másik fél segítségét. A legnagyobb esélye a fél-kooperáció kialakulásának van, vagyis az egyik játékos jellemz®en kihasználja a másikat, pontosabban az


76

100 telj. index = 0,7 telj. index = 0,8 telj. index = 0,9

90

80

Eloszlás [%]

70

60

50

40

30

20

10

0

0

1

2


7.3. ábra. Stratégiapárok kooperációs kategóriák közötti megoszlása a teljesítmény index függvényében

hagyja kihasználni magát. A 7.2. ábra tanulsága, hogy a nagyobb energiafogyasztási tényez® érték serkenti a kooperációt. Ha az α értékét nagyra választjuk, akkor drágává tesszük a kommunikációt, hiszen hatványozottan növeljük a kommunikáció energiafogyasztásának távolságfügg® komponensét. A drága interakció megköveteli tehát, hogy kicsik legyenek a távolságok, amiket át kell hidalni. Ha a szenzorok kooperálnak, akkor ugyanazt a szenzorbázis távolságot több ugrás segítségével tudjuk megtenni, vagyis pontosan az átlagos szenzorbázis távolság csökkenését érjük el. Ugyanakkor el kell mondani, hogy ugyan a magas α értékek serkentik a kooperációt, viszont a szenzorok élettartamát drasztikusan csökkentik. A cél a szenzorok élettartamának növelése, úgyhogy az energiafogyasztási tényez® értékét érdemes alacsonyra választani (vagyis megfelel®en elhelyezni a szenzorokat a területen, ha ez lehetséges), még akkor is, ha ezzel esetleg csökkentjük a kooperáció kialakulásának valószín¶ségét. A teljesítmény index változtatásának hatását szemléltetni kívánó 7.3. ábra azt mutatja, hogy ugyan sokszor kialakul legalább az egyik fél részér®l a kooperáció, viszont annak mértékét a teljesítmény index nem befolyásolja számottev®en. A magasabb teljesítmény indexek valamivel jobb eredményt érnek el a kooperáció kialakulásának szempontjából ugyanúgy, mint ahogy azt az α értékeinél láttuk, viszont jóval kötöttebb rendszert írnak


77

le, vagyis az élettartamok meghosszabbítása ellen hatnak. A 7.4. ábrán egy másik megközelítésben prezentálom a szimulációk eredményeit. A vizsgált teszteseteket egy grakonon ábrázolva azt szeretném megmutatni, hogy mekkora élettartam-növekedést jelent az, ha a szenzorok nem defektív módon játszanak, hanem a Nash-egyensúly diktálta stratégiát követik.

7.4. ábra. Élettartam-növekmények különböz® elrendezések esetén A számmal jelölt elrendezéseknek megfelel® paraméter-hármasokat a 7.2. táblázat tartalmazza. 7.2. táblázat. Szimulációs elrendezések 1 2 3 4 5 Játékosonkénti szenzorszám

10

20

Teljesítmény index

0,8

0,7 0,8

Energiafogyasztási tényez®

3

3

20 2

20

20

0,8 0,8 3

4

6

7

20

40

0,9 0,8 3

3

Látható, hogy bármilyen elrendezést tekintünk is, mindig érdemes Nash-egyensúlyi pontot alkotó stratégiapárokat alkalmazni. Az így elérhet® élettartam-növekmény jelent®s (ezt


78

a növekményt mutatja az oszlopdiagrammok vörös része), minimálisan is 22%-os, de az összes eset átlagát tekintve közel 34%-os. Ez azt jelenti, hogy ismeretlen körülmények közé telepítend® szenzorhálózatunkat érdemes egyensúlyi stratégiával felprogramozni, mert az ezzel az eljárással átlagosan élettartamának harmadával tovább maradhat életben. Az el®z®ekben már láttuk, hogy a maximális Nash-egyensúlyokat stratégiapárok nagy része kooperatívnak tekinthet®, ha a kooperatív és a fél-kooperatív kategóriába es® elemeket egy kalap alá vesszük. Elmondható tehát, hogy az élettartam-növekmények az esetek többségében a kooperatív stratégiapárok el®fordulásának köszönhet®ek, vagyis a kooperáció megjelenése jelent®s mértékben meghosszabbította a szenzorhálózatok élettartamát.

8. fejezet Konklúzió és továbblépési lehet®ségek A dolgozatban a szenzorhálózatokban kialakuló spontán kooperáció kérdéskörét vizsgáltam. Számos modellt és több szimulátort is kidolgoztam, melyek a témakörrel kapcsolatos homályos területeket hivatottak felderíteni. Vizsgálataimat egy egyszer¶ modellen kezdtem el®ször analítikus megoldásokat keresve, majd a problématér b®vülésével a számítógépes szimuláció eszközkészletét használtam fel. Mindazonáltal a problématér méretét korlátoznom kellett, hiszen az alapvet®en végtelen. Mindvégig a játékelmélet fogalmai szerinti kooperációt kerestem, szem el®tt tartva a szenzorhálózatok élettartamának meghosszabítására irányuló célt. Az eredményeim azt tükrözik, hogy az esetek többségében kialakul a kooperáció küls® serkentés nélkül, vagyis spontán módon. Az alkalmazott modellekben a paraméterek változtatásával jó eséllyel kialakítható a kooperáció valamilyen formája, akármelyik általam használt kooperáció fogalmat tekintjük is. Az általam vizsgált rendszereknek három céljuk volt, ezek fontossági sorrendben a következ®k: 1. A szenzoroknak el kellett látniuk a bázis(ok)at megfelel® mennyiség¶ és min®ség¶ mérési eredménnyel. 2. A szenzorhálózatoknak minél hosszabban életben kellett maradniuk kizárólag saját er®forrásaikra támaszkodva. 3. A hosszú élettartamot lehet®ség szerint játékelméleti kooperáció alkalmazásával kellett elérniük. 79

8. FEJEZET. KONKLÚZIÓ ÉS TOVÁBBLÉPÉSI LEHETSÉGEK

80

Azt tapasztaltam, hogy az élettartam és a kooperáció egymástól függetlenül nem vizsgálható, hiszen például az energiafogyasztási tényez® növelésével a kooperációs hajlandóság drasztikusan növekszik, míg a szenzorok élettartama határozottan csökken. Nem mindig igaz tehát, hogy a kooperáció kialakulása az élettartam meghosszabbodásával jár. Ugyanakkor igaz, hogy a leghosszabb élettartamok egyben maximális Nash-egyensúlyok is, vagyis a hosszabb élettartam kialakulásának hátterében a kooperáció áll. A szimulációs paramétereket sorbavéve azokról a következ® mondható el. A teljesítmény

index értéke nincs különösebb hatással a stratégiapárok kooperációs kategóriák közötti eloszlására, vagyis a kooperáció kialakulására. Egy magasabb teljesítmény index érték szigorúbb rendszert ír le, ezért csökkenti a hálózat élettartamát. Az energiafogyasztási tényez® növelésével a kooperációs hajlandóság n®, viszont a kommunikáció is jelent®sebb energiabefektetést igényel. A szenzors¶r¶ség függvényében szintén fordítottan arányos egymással a kooperáció kialakulásának valószín¶sége és a hálózatok élettartama. A szenzorhálózatokkal és azon belül a kooperáció kérdéskörével foglalkozó publikációk közül összehasonlítási alapként a [24]-es cikk szolgálhat. Ebben a cikkben a szerz®k az én eredményeimhez hasonlókat kaptak, ugyanakkor els®sorban a kooperáció kialakulását vizsgálták, kevésbé foglalkoztak a szenzorok élettartamával. Hasonló eredményre jutottak az energiafogyasztási tényez® tekintetében, vagyis a cikk szerint is növeli a kooperáció el®fordulásának valószín¶ségét az α növelése. Továbbá a szenzors¶r¶ség és a kooperáció viszonyát tekintve is hasonló következtetésre juttottak, miszerint a szenzorok számának növelése csökkenti a kooperációs hajlandóságot. Látható, hogy a szenzorhálózatokban kialakuló spontán kooperáció kérdésköre még jócskán tartogat feltárnivalót. A legkézenfekv®bb továbblépési lehet®ségként a szenzorok elhelyezkedési módjának vizsgálatát, vagyis a topológia-vizsgálatot említeném. Ebben a dolgozatban a szenzorokat végig egyenletes eloszlás szerint véletlenszer¶en helyeztem el a síkon, ugyanakkor az eredményekb®l sejthet®, hogy a topológia nagy hatással van mind a kooperáció kialakulására, mind a szenzorok élettartamára. Véleményem szerint érdemes lehet megvizsgálni az átlagos szenzorszenzor és szenzorbázis távolság változtatásának hatását az említett két kritériumra. Másik továbblépési lehet®ségként említeném a nagyobb rendszerek (még több szenzor, hosszabb history, alacsonyabb teljesítmény index, több bázis, stb.) vizsgálatát, amikhez már igen jelent®s számítási kapacitás szükséges. Kissé tágabb értelemben lehetne foglalkozni a biztonságos útválasztással, a biztonságos csomagküldéssel, a szenzorok anonimitásával, stb. a sort még hosszan lehetne folytatni.

Köszönet nyilvánítás Szeretném megköszönni dr. Buttyán Levente áldozatos munkáját, amivel három féléven keresztül egyengette kutatásaim útját és jelent®s mértékben hozzájárult mind a tanulmányaim alatti sikereimhez, mind ezen diplomaterv létrejöttéhez. Kiemelném Holczer Tamás segítségét, a vele folytatott megbeszélések mindannyiszor nagy mértékben el®remozdították a kutatásaimat és segítettek tisztábban látni a problémákat. Köszönet illeti dr. Vajda Istvánt, akinek lényeglátó megjegyzései és kommentárjai segítettek más szemszögb®l is megismerni a vizsgált problémákat. Szeretnék továbbá köszönetet mondani dr. Imre Sándornak, aki mellett el®ször találkoztam a játékelmélet fogalomkörével. Végül, de nem utolsó sorban szeretném megjegyezni, hogy a legnagyobb hálával szüleimnek tartozom, akik lehet®vé tették, hogy egyetemi éveim alatt és a diplomatervezés id®szakában is maximális er®ráfordítással koncentrálhassak a tanulmányaimra.

81

Táblázatok jegyzéke 5.1. A játékosok lépésköltségei . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

5.2. Paraméteres élettartamok . . . . . . . . . . . . . . . . . . . . . . . . . . .

56

5.3. Tranzienseket gyelembe vev® élettartamok . . . . . . . . . . . . . . . . . .

57

6.1. Egydimenziós véletlen szimulációk . . . . . . . . . . . . . . . . . . . . . . .

67

6.2. Kétdimenziós véletlen szimulációk, 10+10 csomópont . . . . . . . . . . . .

68


69


69

6.5. Kétdimenziós véletlen szimulációk, 10+10 csomópont, 5 bázis . . . . . . . .

70

6.6. Kétdimenziós véletlen szimulációk, 20+20 csomópont, 5 bázis . . . . . . . .

70

7.1. Szimulációs paraméterek a továbbfejlesztett modellhez

. . . . . . . . . . .

74

7.2. Szimulációs elrendezések . . . . . . . . . . . . . . . . . . . . . . . . . . . .

77

82

Ábrák jegyzéke 2.1. Szenzor felépítése . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2.2. Szenzorok logikai rétegszerkezete

. . . . . . . . . . . . . . . . . . . . . . .

13

3.1. Útválasztási példa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

3.2. Nem kooperatív viselkedés osztályozása . . . . . . . . . . . . . . . . . . . .

35

4.1. Példa domináns egyensúly számolására . . . . . . . . . . . . . . . . . . . .

48

4.2. Példa Nashegyensúly meghatározására . . . . . . . . . . . . . . . . . . . .

50

5.1. A vizsgált egyszer¶ hálózat . . . . . . . . . . . . . . . . . . . . . . . . . . .

53

5.2. Példa stratégia az utolsó lépés modellhez . . . . . . . . . . . . . . . . . .

59

5.3. A 4096-os stratégia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

60

6.1. Egydimenziós szimmetrikus hálózat . . . . . . . . . . . . . . . . . . . . . .

66

6.2. Kétdimenziós szimmetrikus hálózat . . . . . . . . . . . . . . . . . . . . . .

67

6.3. Kétdimenziós véletlen hálózat, 50+50 csomópont

69

. . . . . . . . . . . . . .

7.1. Stratégiapárok kooperációs kategóriák közötti megoszlása a szenzorok számának függvényében . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

75

7.2. Stratégiapárok kooperációs kategóriák közötti megoszlása az energiafogyasztási tényez® (α) függvényében . . . . . . . . . . . . . . . . . . . . . . . . .

75

7.3. Stratégiapárok kooperációs kategóriák közötti megoszlása a teljesítmény index függvényében . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

76

7.4. Élettartam-növekmények különböz® elrendezések esetén . . . . . . . . . . .

77

83

Irodalomjegyzék [1] J. Rabaey, J. Ammer, J.L. da Silva Jr., D. Patel, PicoRadio: Ad Hoc Wireless Networking of Ubiquitous Low-Energy Sensor/Monitor Nodes, Proceedings of the IEEE

Computer Society Annual Workshop on VLSI, Florida, pp. 9-12., 2000. [2] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, Wireless Sensor Networks: a Survey, Computer Networks, Vol. 38, pp. 393-422., 2002. [3] Holczer Tamás, Schaer Péter, Spontán kooperáció kialakulása különböz® fennhatóság alá tartozó szenzorhálózatok között, Kari TDK dolgozat, Hálózatszimuláció

és teljesítményvizsgálat szekció, 2004. [4] http://robotics.eecs.berkeley.edu/∼pister/SmartDust, 2005. április [5] David Wagner, Resilient Aggregation in Sensor Networks, SASN'04, Washington, 2004. [6] Szép Jen®, Forgó Ferenc, Bevezetés a játékelméletbe, Közgazdasági és Jogi Könyvkiadó, Budapest, 1974. [7] Rahul C. Shah, Jan M. Rabaey, Energy Aware Routing for Low Energy Ad Hoc Sensor Networks, IEEE Wireless Communications and Networking Conference (WCNC), 2002. [8] E. Royer, C.K. Toh, A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks, IEEE Personal Comm., pp. 46-55., 1999. [9] C.E. Perkins, P. Bhagwat, Highly Dynamic Destination Sequenced Distance Vector Routing (DSDV) for Mobile Computers, Comp. Commun. Rev., pp. 234-244., 1994.

84

IRODALOMJEGYZÉK

85

[10] T. Clausen, P. Jacquet, Optimized Link State Routing Protocol, Internet Draft,

http://www.ietf.org/rfc/rfc3626.txt, 2003. [11] C. Perkins, E. Royer, Ad Hoc On Demand Distance Vector Routing, Proc. 2nd IEEE

Workshop on Mobile Computing Systems and Applications (WMCSA), 1999. [12] D.B. Johnson, D.A. Maltz, Dynamic Source Routing in Ad Hoc Wireless Networks,

Mobile Computing, Kluwer, pp. 153-181., 1996. [13] C. Intanagonwiwat, R. Govindan, D. Estrin, Directed Diusion: A Scalable and Robust Communication Paradigm for Sensor Networks, IEEE/ACM Mobicom, pp. 5667., 2000. [14] Buttyán Levente, Holczer Tamás, Schaer Péter, Kooperációra ösztönz® mechanizmusok többugrásos vezeték nélküli hálózatokban, Híradástechnika, 2004. [15] Philipp Obreiter, Birgitta König-Ries, Michael Klein, Stimulating Cooperative Behaviour of Autonomous Devices - An Analysis of Requirements and Existing Approaches, 2nd International Workshop on Wireless Information Systems

(WIS2003), France, 2003. [16] N.B. Salem, L. Buttyán, J.-P. Hubaux, M. Jakobsson, A Charging and Rewarding Scheme for Packet Forwarding in Multi-Hop Cellular Networks, In Proceedings of

the 4th ACM Symposium on Mobile Ad Hoc Networking and Computing (MobiHOC), Maryland, 2003. [17] L. Buttyán, J.-P. Hubaux, Stimulating Cooperation in Self-Organizing Mobile Ad Hoc Networks, ACM/Kluwer Journal on Mobile Networks and Applications (MONET), 2003. [18] M. Jakobsson, J.-P. Hubaux, L. Buttyán, A Micro-Payment Scheme Encouraging Collaboration in Multi-Hop Cellular Networks, In Proceedings of the 7th International

Financial Cryptography Conference, Guadeloupe, 2003. [19] S. Zhong, Y.R. Yang, J. Chen, Sprite: A Simple, Cheat-Proof, Credit-Based System for Mobile Ad Hoc Networks, In Proceedings of the 22nd Annual Joint Conference of

the IEEE Computer and Communications Societies (Infocom), 2003.

IRODALOMJEGYZÉK

86

[20] L. Buttyán, J.-P. Hubaux, Nuglets: A Virtual Currency to Stimulate Cooperation in Self-Organized Ad Hoc Networks, Technical Report DSC/2001/001, Swiss Federal

Institute of Technology, Lausanne, 2001. [21] S. Marti, T.J. Giuli, K. Lai, M. Baker, Mitigating Routing Misbehaviour in Mobile Ad Hoc Networks, Mobile Computing and Networking, pp. 255-265., 2000. [22] P. Michiardi, R. Molva, Making Greed Work in Mobile Ad Hoc Networks, Technical Report, Institut Eurécom, 2002. [23] S. Buchegger, J.Y.L. Boudec, Performance Analysis of the CONFIDANT Protocol: Cooperation of Nodes Fairness in Distributed Ad Hoc Networks, In Proceedings

of IEEE/ACM Workshop on Mobile Ad Hoc Networking and Computing (MobiHOC), pp. 80-91., 2002. [24] M. Félegyházi, J.-P. Hubaux, L. Buttyán, Cooperative Packet Forwarding in MultiDomain Sensor Networks, In Proceedings of the First International Workshop on

Sensor Networks and Systems for Pervasive Computing (PerSeNS), 2005. [25] V. Srinivasan, P. Nuggehalli, C.F. Chiasserini, R.R. Rao, Cooperation in Wireless Ad Hoc Networks, In Proceedings of IEEE INFOCOM, San Francisco, 2003. [26] M. Félegyházi, J.-P. Hubaux, L. Buttyán, Nash Equilibria of Packet Forwarding Strategies in Wireless Ad Hoc Networks, to appear in IEEE Transactions on Mobile

Computing [27] L. Buttyán, T. Holczer, P. Schaer, Spontaneous Cooperation in Multi-Domain Sensor Networks, 2nd European Workshop on Security and Privacy in Ad hoc and Sensor

Networks, submitted for publication, 2005.

Budapesti M szaki és Gazdaságtudományi Egyetem

Recommend Documents