Útvonalválasztó protokollok vezeték nélküli szenzorhálózatokban ÁCS GERGELY, BUTTYÁN LEVENTE Budapesti Mûszaki és Gazdaságtudományi Egyetem, Híradástechnikai Tanszék, CrySyS laboratórium {acs, buttyan}@crysys.hu Lektorált
Kulcsszavak: szenzorhálózatok, útvonalválasztás, protokollok, hálózati és mûködési modellek A szenzorhálózatok változatos alkalmazásai különbözô követelményeket támasztanak az útvonalválasztó protokollokkal szemben. A különbözô követelményeknek köszönhetôen igen sok javasolt protokoll található az irodalomban. Ebben a cikkben rendszerezzük ezeket a útvonalválasztó protokollokat, és minden családból bemutatunk egy prominens képviselôt. A cikk újdonsága a rendszerezéshez használt szempontrendszer, mely a protokollok eddigieknél részletesebb taxonómiáját eredményezi.
1. Bevezetés
2. Osztályozási szempontrendszer
A szenzorhálózatokat egyrészrôl a mérést végzô szenzorcsomópontok, másrészrôl az adatokat begyûjtô bázisállomások (báziscsomópontok) alkotják. Míg a rendkívül nagy számú, és általában homogén szenzorcsomópontok tipikusan alacsony energiaellátottsággal és számítási kapacitással rendelkeznek, addig a kis számú bázisállomások erôforrása legtöbbször korlátlan. Az egyes szenzorcsomópontok egymással és a bázisállomásokkal egyaránt vezetéknélküli kapcsolatokon kommunikálnak, amelyeknek az energiaigénye jóval magasabb mint a csomópontok által végzett egyszerû számításoké, valamint egy üzenet elküldéséhez körülbelül kétszer annyi energia szükséges mind annak vételéhez. Ezekbôl következik, hogy egy szenzorcsomópont által küldött üzenet útvonala egy bázis felé korántsem mellékes: a túl hosszú, illetve alacsony teleptöltöttségû csomópontokat tartalmazó útvonalak csökkentik a hálózat élettartamát, valamint a túl sok csomópontot tartalmazó útvonalak adott esetben növelhetik az üzenet késleltetését. Sajnos ezen követelmények sokszor ellentmondanak egymásnak: ha mindig a legrövidebb útvonalon továbbít egy szenzorcsomópont a bázis felé, akkor az a köztes csomópontok rövid élettartamához, és bizonyos értelemben a hálózat élettartamának rövidüléséhez vezet, holott ez jelentené a legkisebb energiafogyasztást és késleltetést globális értelemben. Összességében az útvonalválasztás célját maga az alkalmazás határozza meg; például valós idejû alkalmazásoknál a minimális késleltetés, míg statisztikai számításokat végzô alkalmazásoknál a hosszú élettartam lehet elsôdleges cél. A sokféle alkalmazásra így különbözô útvonalválasztó protokollokat javasoltak [1], amelyek az útvonalválasztás céljában, valamint ezen célok elérésre használt technikákban különböznek, ahol a technikákat a hálózat által támasztott technológiai korlátok alakítják.
Az útvonalválasztó protokollok nagy száma a következô természetes kérdést vetheti fel egy alkalmazásfejlesztô számára: Melyik protokoll felel meg legjobban az alkalmazásom számára? E kérdés megválaszolásához az szükséges, hogy az összes útvonalválasztó protokollt egy olyan közös szempontrendszerbe helyezzük, ahol a protokollok összehasonlíthatóvá válnak. Rendszerezésünk alapját egyrészrôl a hálózat technológiáját és a protokollok mûködését leíró rendszermodell, másrészrôl a protokoll által kitûzött cél alkotja. A rendszermodell tovább osztható a hálózati technológiát leíró hálózati modellre, valamint a mûködési tulajdonságokat leíró mûködési modellre.
LXI. ÉVFOLYAM 2006/12
2.1. A hálózati modell 2.1.1. Bázisállomás A bázisállomások nagy számítási kapacitású és korlátlan energiaellátottsággal rendelkezô hálózati eszközök. A következô tulajdonságok viszont már hálózatonként eltérôek lehetnek, és így az útvonalválasztó protokoll mûködését is befolyásolják. • Szám: A bázisállomások száma lehet egy, illetve egynél több. A legtöbb gyakorlati esetben a tipikus számuk egy, de több bázisállomás növeli az adatbegyûjtés robusztusságát, valamint csökkenti annak késleltetési idejét. Az egy bázisállomást tartalmazó esetben (ha nincs egyéb igény a szenzorcsomópontok közötti explicit kommunikációra) a végcél minden üzenet számára ugyanaz, míg egynél több számú bázisállomás esetében, a cél lehet több, nem feltétlen minden üzenetre egyezô bázisállomás. • Mobilitás: Egy bázisállomás lehet fix (helyhezkötött), korlátozott mértékben mobilis, illetve korlátlanul mobilis. Legtöbbször olyan hálózatokban mobilisak a bázisállomások, ahol a számuk kevés, mégis nagyobb robusz3
HÍRADÁSTECHNIKA tusságra és kisebb késleltetésre van szükség az ugyanolyan számú de helyhez kötött bázisállomások esetéhez képest. A mobilitás miatt az útvonalválasztás által kialakított topológia idôben nagy mértékben változhat, ami túlterheltséget jelenthet a hálózati rétegben. • Jelenlét: Néhány alkalmazásnál a bázisállomások nincsenek folyamatosan jelen (például kikapcsolják ôket karbantartási célból), míg más esetekben a jelenlét folyamatosan biztosított. Az idôszakos leállásokat az útvonalválasztó protokollnak támogatnia kell, mivel a bázis jelenlétének hiánya nem feltétlen ebben az esetben nem hiba, és így az üzenetet nem kell eldobni vagy átirányítani, hanem azokat esetleg várakoztatni kell. • Lefedettség: A bázisállomás nagy erôforráskészlete lehetôvé teheti egy erôs antenna alkalmazását is, amivel esetleg az egész hálózat lefedhetô, és így minden csomópontot közvetlenül elérhet a bázisállomás (ha nincs árnyékoló akadály). Ekkor nincsen szükség a bázis és a szenzorcsomópontok közötti útvonalválasztásra. Megjegyezzük azonban, hogy a legtöbb gyakorlati esetben a lefedettség nem teljes. 2.1.2. Szenzorcsomópont Szenzor alatt a továbbiakban a vezérlô áramkörök és rádiós egység, az érzékelô egység, és a szükséges telep együttesét értjük. A szenzorok kis számítási kapacitású és korlátozott energiaellátottsággal rendelkezô, legtöbbször helyhez kötött hálózati eszközök. A következô tulajdonságok viszont már hálózatonként eltérôek lehetnek, és így az útvonalválasztó protokoll mûködését is befolyásolják. • Elhelyezés: A szenzorok lehelyezése lehet véletlenszerû, vagy determinisztikus. Sok esetben az útvonalválasztó protokollnak alkalmazkodnia kell a kötött hálózati szerkezethez (például út mentén szabályosan elhelyezett szenzorok), más esetben (helikopterrôl kiszórt szenzorok) pedig alapozhat arra a feltevésre, hogy a szenzorok egyenletesen véletlenül vannak elosztva. • Átviteli energia: Az átviteli energia szintje lehet állítható, vagy pedig konstans, vagyis a szenzor minden üzenetet ugyanazon az energiaszinten sugároz. Ez elsôsorban a szomszédos csomópontok energiában mért távolságának a meghatározásában játszik szerepet, hiszen sok protokoll ezt használja a szomszédokhoz rendelt költségek megállapításához. • Lefedettség: Szélsôséges esetben, ha egy szenzor nagy energiával ad, bármely más csomópontot közvetlenül elérhet a hálózatban. Ennek kihasználása azonban általában csak kis méretû hálózatokban lehet hatékony a nagy energiaigény és a megnövekedett interferencia miatt. • Címzés: Az útvonalválasztás feladata a szenzorhálózatokban a bázistól (vagy ritkán más szenzortól) ér4
kezô kérések eljuttatása ahhoz a csomópont(ok)hoz, amely rendelkezik a kért adattal, valamint ezen adat visszajuttatása a bázishoz. Ennek megfelelôen beszélhetünk a kérés, illetve a válasz kezelése során alkalmazott címzésrôl: – Kérés: A kérés címzése történhet a kért adat alapján (Mi az átlaghômérséklet?), vagy a kért adat vagy szenzor pozíciója alapján (Mi a hômérséklet az (x,y) helyen?). – Válasz: A válasz címzése történhet a bázis vagy szenzor pozíciója alapján (Válasz az (x,y) helyen levô bázishoz), vagy a választ váró csomópont lokális, vagy globális azonosítója alapján. Utóbbi esetben, a kérés vétele során minden szenzor megjegyezi a kérést küldô szomszéd azonosítóját, és ennek a szomszédnak továbbítja a választ visszafelé. • A MAC réteg által nyújtott szolgáltatás: A MAC réteg gondoskodhat a szomszédos csomópontok felderítésérôl (ahol a szomszéd definíciója változó), illetve ezen felül, támogathatja a szomszédok költségeinek megállapítását (ahol a költség definíciója szintén protokollonként eltérô). Néhány útvonalválasztó protokoll integrálva van a MAC réteggel a gyorsabb és energiatakarékos mûködés végett (cross layer design). Viszont a legtöbb esetben a MAC réteg nem felel ezen feladatokért, és ezért magának az útvonalválasztó protokollnak a feladata a szomszédok és azok költségeinek megállapítása. 2.2. A mûködési modell Az útvonalválasztó protokollok a következô ortogonális mûködési tulajdonságokkal jellemezhetôek: • Kommunikációs minta: Az útvonalválasztó protokoll támogathatja a szenzorok közötti, a bázis és szenzorok közötti, valamint szenzorok és bázis közötti kommunikációt. – Szenzor–szenzor kommunikáció: Ezt a kommunikációs mintát elsôrorban az ad-hoc hálózatok számára javasolt protokollok támogatják, szenzorhálózatokban ilyen kommunikációra ritkán van szükség. – Bázis–szenzor kommunikáció: A bázis felôl érkezô kérések irányítása során szükséges ennek a kommunikációs mintának a támogatása, mely azt a képességet jelenti, hogy a bázis közvetlenül vagy közvetve bármely szenzornak tud üzenetet küldeni. – Szenzor–bázis kommunikáció: A válaszok irányítása során szükséges ennek a mintának a támogatása, mely azt a képességet jelenti, hogy minden szenzor képes közvetlenül vagy közvetve bármely bázisnak üzenetet küldeni. Minden egyes minta esetén a kommunikáció típusa lehet unicast (egy-egy), multicast (egy-több), reverse-multicast (több-egy), illetve anycast (egyLXI. ÉVFOLYAM 2006/12
Útvonalválasztó protokollok... bármely). Anycast kommunikációra például akkor lehet szükség amikor a bázis adatot kérdez a hálózattól, és nem lényeges, hogy pontosan melyik szenzor válaszol a kérésre, hanem bárki válaszolhat, aki rendelkezik a kért adattal. • Hierarchia: A hierarchikus protokollok esetében az egyes szenzorok (logikai) hierarchiaszinteken helyezkednek el. A szenzorok az alacsonyabb szinten levô szenzoroktól fogadnak üzeneteket, ezeket aggregálják saját adataikkal, és az aggregátumot továbbítják a magasabb hierarchiaszinten levô szenzoroknak. A hierarchia tetején a bázis található. A hierarchia kialakítása lehet statikus vagy dinamikus. Utóbbi esetben, a szenzorok dinamikusan választanak aggregátorokat, és ennek az aggregátor csomópontnak küldenek minden üzenetet. Az aggregátorok további aggregátorokat választanak, és így tovább. A hierarchia kialakításának célja a hálózat élettartamának növelése. A nem-hierarchikus protokollok esetén az egyes csomópontok bármely csomóponttól fogadnak üzenetet aggregálásra, így minden csomópont viselkedhet aggregátorként. • Kézbesítési módszer: A legtöbb protokoll egyetlen útvonalat választ a bázis felé, s ezen minden üzenet egyetlen példányát továbbítja (egy/egy). Néhány protokoll azonban a robusztusság érdekében több útvonalat is választ, s vagy minden üzenetet ezen útvonalak egyikén továbbít (több/egy), vagy minden üzenetet minden útvonalon továbbít (több/több). Elôbbi esetben, a továbbításra használt útvanal kiválasztása lehet determinisztikus vagy véletlenszerûen. • Számítás: Az egyes szenzorok vagy maguk határozzák meg lokálisan a következô csomópontot a bázis felé (decentralizált), vagy pedig minden csomópont elküldi a szomszédossági listáját a bázisnak, amely globálisan meghatározza minden egyes szenzornak a következô csomópontot a bázis felé (centralizált). Az utóbbi optimális megoldást nyújt, viszont ehhez nagy mértékû hálózati kommunikáció szükséges, amely csak kevés számú csomóponttal rendelkezô és fix topológiájú hálózatoknál használható hatékonyan. A szenzorok csak a szomszédaikkal tartják a kapcsolatot, ahol a szomszéd definíciója változó lehet. Legegyszerûbb esetben, a szenzorok azt tekintik szomszédnak, akitôl útvonalválasztó üzenetet kapnak. Más esetekben explicit HELLO üzenetek segítségével derítik fel a szomszédaikat. Ekkor minden csomópont egy bizonyos energiaszinten küld egy HELLO üzenetet többesküldéssel (broadcast), és minden csomópont azt tekinti szomszédnak akinek HELLO üzenetét hallotta. Ez a mechanizmus lehet része az útvonalválasztó protokollnak, vagy pedig az alsóbb protokollrétegben (például MAC réteg) lehet megvalósítva. • Állapot: Az egyes protokollok futtatáskor szükséges lehet minden csomópontnak valamilyen információt tárolni az aktuális állapotról (például a saját költséLXI. ÉVFOLYAM 2006/12
gét, ki a következô csomópont a bázis felé, annak mi a költsége stb.) Ezzel szemben néhány protokoll semmilyen, vagy csak elhanyagolható mennyiségû állapotinformációt tárol. Utóbbi esetben, minden csomópont az üzenetben elhelyezkedô információ, vagy minimális lokálisan tárolt állapotinformáció segítségével (például a szomszédos csomópontok pozíciói) képes meghatározni a következô csomópontot a bázis felé. • Következô szomszéd választása: „Az összes protokoll közös tulajdonsága, hogy a csomópontok lokálisan, a saját információik alapján választják a következô csomópontot a továbbítandó csomag útján. A választás történhet: véletlenszerûen, az üzenet tartalma alapján, az üzenetben szereplô geometriai pozíció alapján, hierarchia szintek alapján, illetve néhány protokollban a csomópontok az üzeneteket többesszórással továbbítják, és a szomszédok maguk döntenek a továbbításról.” • Riportolási modell: A riportolási modell három féle lehet, ahol a csoportosítás alapját az ok adja, ami a forrásszenzorokat üzenetküldésre készteti: – Idôvezérelt: A szenzorok szabályos idôközönként, vagy egy bizonyos idôpontban válaszolnak. Az idôvezérelt protokoll támogathat folytonos (periodikus) vagy idôben egyszeri jelentést, komplex (összetett típusú) vagy egyszerû (atomi típusú) adatok jelentését, aggregálható vagy nem aggregálható adatok jelentését, illetve replikált (több szenzornál megtalálható) vagy egyedi (egyetlen szenzornál megtalálható) adat jelentését. – Kérésvezérelt: A szenzorok a bázis kérésére válaszolnak. A kérésvezérelt protokoll támogathatja komplex vagy egyszerû adatok jelentését, aggregálható vagy nem aggregálható adatok jelentését, illetve replikált vagy egyedi adat jelentését. – Eseményvezérelt: A szenzorok egy bizonyos esemény hatására küldenek üzenetet a bázis felé. Az eseményvezérelt protokoll támogathatja komplex vagy egyszerû adatok jelentését, aggregálható vagy nem aggregálható adatok jelentését, illetve replikált vagy egyedi adat jelentését. Néhány protokoll több csoportba is tartozhat, ha többféle riportolási modellt is támogat. 2.3. A protokoll célja Minden útvonalválasztó protokoll alapvetô célja az üzenet eljuttatása a forrástól a célig. Ez történhet valós idejû követelményekkel együtt, amikor az üzenetnek egy bizonyos idôn belül el kell érnie a célt, vagy pedig valós idejû követelmények nélkül. Utóbbi esetben a sikeresség egy mérôszáma lehet a sikeresen kézbesített üzenetek száma, míg az elôbbi esetben a sikerességet az adott idôn belül sikeresen kézbesített üzenetek száma méri. A protokolloknak az elôbbivel párhuzamos célja lehet a hálózat élettartamának maximalizálása, aminek a 5
HÍRADÁSTECHNIKA mérôszáma már nem egyértelmû. Ha minden csomópont egyenrangú, akkor a hálózat élettartama lehet az elsô csomópont mûködésképtelenségéig eltelt idô, vagy akár az utolsó csomópont mûködésképtelenségéig eltelt idô. Ritka esetekben, amikor csomópontok nem egyenrangúak, akkor a magasabb prioritású csomópontokra érvényesek ezek a megállapítások. Az alkalmas metrika megválasztása alkalmazásfüggô.
3. Protokollok Amint látható, a protokollok csoportosítása többféleképpen lehetséges. A táblázatokban felsoroltuk a létezô jelentôsebb útvonalválasztó protokollokat, ahol az 1. táblázat tartalmazza az egyes protokollok rendszerezését a hálózati modell és a kitûzött cél tekintetében, a 2. táblázat pedig ugyanezen protokollok mûködési modell szerinti osztályozását. A modellek szerint megegyezô protokollokat egyként kezeltük, összefoglaló nevük végére csillagot tettünk. Az egyes cellák tartalma a fentebb leírtak szerint értelmezhetô, az egyetlen csillagot tartalmazó cella jelentése, hogy a protokoll az adott tulajdonság minden értékével rendelkezik. A következôkben a protokollokat aszerint osztjuk családokra, hogy a csomópontok hogyan választja következô csomópontot a továbbítandó csomag útján, és minden így nyert családból bemutatunk egy reprezentáns protokollt, amelyeket részletesebben is ismertetünk. 3.1. Következô csomópont választása az üzenet tartalma alapján Ezek a protokollok csupán a kérésben szereplô kért adat alapján döntenek arról, hogy melyik csomópontnak továbbítsák a kérést. Ez a modell illeszkedik legjobban a szenzorhálózatokhoz, hiszen a bázis többnyire nem egy konkrét szenzort akar lekérdezni, hanem egy bizonyos adat iránt érdeklôdik. Ezen protokollok, paradigmák közül a Directed Diffusion [2] protokolt ismertetjük röviden. A Directed Diffusion több más protokoll alapjául szolgált (Energy Aware Routing, GBR stb.), így az itt leírtak részben azokra is érvényesek. A bázis kezdetben elárasztja kérésével az egész hálózatot, amely tartalmazza a kért adatot leíró attribútumérték párokat. A kérés vételekor a csomópontok gradienseket állítanak be a kérést küldô csomópontra. A forrás így az üzeneteket ezen gradiensek mentén továbbítják a bázis felé, egy üzenetet akár több gradiensen (több szomszédnak) küldve. A paradigma jól alkalmazható nyomkövetési alkalmazásoknál, és csak a közvetlen szomszédok egyértelmû címzését követeli meg. A gradiens minden csomópontnál definiálja a keresett adatot, amire illik a keresett attribútumérték pár, és a következô csomópontot, akinek az adatot majd tovább kell küldeni a bázis felé. Minden gradienshez egy súly van rendelve, amely súly egyenesen arányos a rajta küldött adat mennyiségével. Kezdetben a közbensô 6
csomópontok több szomszédtól is kaphatnak egyezô kérést, így ennek megfelelôen több gradienst is beállítanak a bázis felé. Idôvel a legjobb minôségû út mentén a bázis növeli a gradiensek súlyát, amivel ezen utakon növeli a forgalmat, míg másokon csökkenti. A közbensô csomópontok aggregálják a küldött adatot, és az aggregátumot továbbítják a megfelelô gradiensek mentén a gradiens súlyával arányos sebességgel. A bázis periodikusan újraküldi a kérést, amivel életben tartja az empirikusan megfelelô minôségû útvonalakat. Az egyes csomópontok különbözô cache technikákkal növelik a protokoll robusztusságát és teljesítményét. A protokoll hátránya, hogy a kezdeti elárasztás költséges, és az empirikusan megfelelô minôségû utak kiválasztásáig a hálózat energiafogyasztása magas. 3.2. Véletlenszerûen választott következô csomópont A véletlenszerûen választott következô csomópont mögötti szándék elsôsorban a robusztusság és a egyenlô terheléselosztás elérése, illetve megközelítése. Ezek a protokollok nagyban alapoznak arra a tényre, hogy a szenzorok homogén, egyenletesen lehelyezett eszközök. Ezek közül az Energy Aware Routing [5] protokollt ismertetjük. Az Energy Aware Routing protokoll fô célja a hálózat élettartamának növelése az egyenlô terheléselosztás megközelítésével. A protokoll futása során a cél csomópont (bázis) kezdeményezi a kommunikációt, amikor arra igény van. A szenzorok igyekeznek mindig különbözô szomszédot választani a továbbításra. A választás véletlenszerû, ahol egy adott szomszéd választásának a valószínûsége fordítottan arányos annak költségével. A költség függ az adott szomszéd aktuális maradék energaszintjétôl, illetve a hozzá történô üzenettovábbításhoz szükséges energiától. A protokoll a szomszédok listáját, és az elérésükhöz szükséges energiát a MAC rétegtôl kapja. A protokoll három fázisból áll: inicializálás, üzenettovábbítás, útvonal karbantartása. I. Inicializálás Korlátozott elárasztás segítségével minden csomópont felépíti az útvonalválasztó tábláját, vagyis minden csomópont megállapítja a lehetséges útvonalakat a cél felé, és azok költségét. 1. A cél elárasztja a hálózatot a forrás irányába egy kérés üzenettel, aminek a költségmezejét nullára állítja: Cost = 0 2. Minden közbensô csomópont csak azon szomszédjainak továbbítja a kérést, amelyek a forráshoz közelebb, a céltól viszont távolabb helyezkednek el. Formálisan Ni csak akkor küldi el a kérést Nj szomszédjának, ha a következô egyenlôtlenségek teljesülnek: d(Ni , NS) ≥ d(Nj , NS), d(Ni , ND) ≤ d(Nj , ND), ahol d(Ni , Nj ) az Ni és Nj csomópontok távolságát jelenti, és NS a forrás, ND pedig a célcsomópont azonosítója. LXI. ÉVFOLYAM 2006/12
1. táblázat Hálózati modell és célkitûzés
Útvonalválasztó protokollok...
LXI. ÉVFOLYAM 2006/12
7
2. táblázat Mûködési modell
HÍRADÁSTECHNIKA
8
LXI. ÉVFOLYAM 2006/12
Útvonalválasztó protokollok... 3. A kérés vétele során Nj kiszámítja az Ni -n keresztül haladó útvonal költségét a következôképpen: CNj,Ni = Cost + Metric(Nj , Ni ), ahol Metric(Nj , Ni ) az Nj és Ni közötti metrikát jelenti (lásd késôbb). 4. A magas költségû útvonalakat Nj nem veszi figyelembe és eldobja a megfelelô kérést, csak az alacsony költségû csomópontokat adja hozzá az útvonalválasztó táblákhoz: FTj = {i |CNj,Ni ≤ α (mink CNj,Nk)} 5. Minden Nj csomópont egy valószínûséget rendel minden szomszédjához az FTj táblában:
6. Nj kiszámolja a célhoz vezetô utak átlagos költségét (amelyek az FTj útvonalválasztó táblában szerepelnek):
7. Ez az átlagos költség lesz a továbbítandó kérés új költégértéke: Cost = Cost(Nj ), majd az új kérést Nj továbbítja a forrás fele a 2. lépés szerint. II. Üzenettovábbítás 1. A forrás elküldi az üzenetet a táblájában szereplô egy szomszédjának, ahol a szomszédot a hozzá rendelt valószínûséggel választja. 2. Minden közbensô csomópont hasonlóképpen választja ki a következô csomópontot a cél felé, vagyis választ egy szomszédot a táblájából a hozzá rendelt valószínûséggel. 3. Ez folytatódik addig, ameddig az üzenet eléri a célt (bázist). III. Útvonal karbantartása Az útvonal karbantartása minimális; nem túl gyakran a cél (bázis) elárasztással indirekt frissíti a szenzorok útvonalválasztó tábláját. A metrikát, amit az I.3 pontban használunk a következôképpen számoljuk ki: Ci,j = e i,jαRi β, ahol Ci,j az Ni és Nj csomópontok közötti költségmetrika, e i,j az egy üzenet átviteléhez szükséges energia Ni -bôl Nj -be, Ri pedig Ni csomópont maradék energiája (az aktuális teleptöltöttség) normalizálva a csomópont indulási energiájával (kezdeti teleptöltöttség). Az α és β változtatható paraméterek, attól függôen, hogy a hálózat élettartamát vagy a globális energiafogyasztást akarjuk minimalizálni. A protokoll a Directed Diffusion paradigmához képest átlagosan 21,5%-kal több energiát spórol, és 44%kal növeli a hálózat élettartamát (ha a hálózat élettartamát az elsô szenzorcsomópont kimerüléséig eltelt idôvel számítjuk). Hátránya az egyes csomópontok esetleges komplikált címzése, illetve az inicializálási fázis megnövekedett kommunikációs költsége a Directed Diffusion protokollhoz képest. LXI. ÉVFOLYAM 2006/12
3.3. Következô csomópont választása geometriai információ alapján Az útvonalválasztó protokollok ezen családja a szomszédok ismert geometriai pozíciói és a cél pozíciója alapján döntenek a következô csomópontról a cél felé, ami lehet egy régió vagy egy konkrét csomópont. Ezzel elkerülik az elárasztás okozta többletterhelést, viszont többletköltséget jelenthet a pozíciók megállapítása, ami történhet statikusan, elôreprogramozott módon, vagy valamilyen pozíció-meghatározó rendszer segítségével (pl. GPS). Többnyire mind a kérés, mind pedig a válasz útvonalirányítására ugyanazt a technikát használják. A legtöbb decentralizált pozíció alapú protokoll közös problémája a lokális minimum feloldása, amikor minden szomszédos csomópont távolabb helyezkedik el a céltól mint maga a továbbító csomópont. Ezen probléma feloldására különbözô technikákat használnak az egyes protokollok. Itt most a GEAR (Geographical and Enegy Aware Routing) [6] protokollt ismertetjük vázlatosan. A GEAR esetében a csomópontok csak bizonyos szomszédaiknak továbbítják a kérést, így több energiát spórolnak meg mint a Directed Diffusion. A válasz továbbítása történhet vagy a kéréshez hasonló módon, vagy pedig a Directed Diffusion esetében leírt módon. Minden csomópont a célcsomópontra (forrás) nyilvántart egy becsült és egy tanult költségértéket. Az utóbbi felelôs a lyukak megkerüléséért és a becsült költségérték finomításának tekinthetô. Ha az útvonalban nincsenek lyukak (minden csomópontnak van a célhoz közelebb esô szomszédja), akkor a két költségérték megegyezik. A protokoll két fázisból áll: üzenettovábbítás a célterület felé, valamint üzenettovábbítás a célterületen belül. I. Üzenettovábbítás a célterület felé Egy közbensô N csomópont a célterülethez közelebb esô szomszédokból választja ki azt a következô csomópontot a cél felé, amelynek tanult költsége a legkisebb. Ha ilyen nem létezik, akkor azt a szomszédot választja az összes közül, amelynek becsült költsége a legkisebb. Kezdetben a tanult költség a célterületre megegyezik a becsült költséggel, ahol a becsült költség formulája a következô: c(Ni , R) = αd(Ni , R) + (1 – α)e(Ni ), ahol d(Ni , R) a szomszédos Ni csomópont távolsága a célterület középpontjától, e(Ni ) az Ni csomópont normalizált maradék energiája, α pedig egy állítható paraméter. Minden csomópont kiszámítja saját becsült költségét, majd elküldi minden szomszédjának, így minden csomópont értesül minden szomszédjának a becsült költségérôl. Kezdetben a tanult költség minden Ni csomópontra egy adott célterületre h(Ni , R) = c(Ni , R). Miután egy N csomópont elküldte az üzenetet a minimális tanult költségû szomszédjának aminek az azonosítója Nmin, frissíti a saját tanult költségét a következô módon: h(N, R) = h(Nmin, R) + C(N, Nmin), ahol C(N, Nmin) az üzenet továbbításának költsége N-bôl Nmin-be (lehet a küldéshez használt energia menynyisége, a távolság, a normalizált maradék energia, 9
HÍRADÁSTECHNIKA illetve ezek kombinációi). Így, ha az utat n csomópont alkotja, akkor az útvonal tanult költsége n lépésben konvergál az útvonal valódi költségéhez. A csomópontok a tanult költségük értékét bizonyos idôközönként elküldik az összes szomszédjuknak. Így a tanult költségek használata a megfelelô frissítési technikával lehetôséget adnak a lyukak kikerülésére. A GEAR nem csupán hosszabb élettartamot biztosít a szenzorhálózatoknak mint más pozíció alapú útvonaválasztó protokollok, de a kézbesített csomagok száma akár 80%-kal több lehet, mint más pozíció alapú protokolloknál. II. Üzenettovábbítás a célterületen belül Miután az üzenet elérte a célterületet, az ottani csomópontok korlátozott vagy pedig rekurzív elárasztásos technikát használnak az üzenet elterjesztésére a területen belül. Ha a csomópontok ritkán helyezkednek el, akkor a korlátozott elárasztás, míg sûrûn elhelyezett csomópontok esetén a rekurzív elárasztásos technika javasolt. Az utóbbi esetben a területet négy, körülbelül egyenlô alterületre osztjuk, és minden alterületre továbbítjuk az üzenet egy másolatát. Ez a felosztásos folyamat rekurzív módon addig folytatódik, amíg csak egy csomópont marad egy alterületen belül. 3.4. Hierarchia szint alapján választott következô csomópont A hierarchikus protokollok esetében minden csomópont a hierarchiában fentebb elhelyezkedô csomópontnak (aggregátor) küldi az üzenetet, ahol a hierarchia csúcsán a bázis helyezkedik el. Az egyes csomópontok a bejövô üzeneteket aggregálás után küldik tovább, amivel jelentôsen csökkenthetik az adatforgalmat, így energiát spórolnak meg, aminek eredménye a hálózat megnövekedett élettartama. A hierarchikus protokollok másik nagy elônye, hogy jól skálázhatóak. Az egy aggregátornak továbbító csomópontok halmazát klaszternek, míg az aggregátort klasztervezetônek is nevezik. Klasztervezetôknek mindig olyan csomópontokat választanak (statikusan vagy dinamikusan), amelyek nagyobb erôforrással (általában nagyobb teleptöltöttséggel) rendelkeznek, mivel a többi csomóponthoz képest nagyobb forgalmat bonyolítanak le és több számítást végeznek. A hierarchikus útvonalválasztó protokollok alappillére az klaszterek kialakítása és a klasztervezetô megválasztása, majd erre épülve az útvonalválasztás megvalósítása a klasztervezetôk felé. A következôkben a LEACH (Low Energy Adaptive Clustering Hierarchy) [3] protokollt vázoljuk fel. A LEACH protokollban a csomópontok dinamikusan, elosztott módon alakítják ki a klasztereket. A LEACH futásakor minden klasztervezetô véletlenszerûen választódik meg, és ez a szerep dinamikusan rotálódik az egyenletes terheléselosztás végett. Minden klasztervezetô a klaszterbôl érkezô üzeneteket aggregálja, majd az aggregátumot közvetlenül elküldi a bázisnak. Így a LEACH feltételezi, hogy minden csomópont ké10
pes elérni a bázisállomást. A LEACH TDMA/CDMA csatornahozzáférési modellt követ a klaszteren belüli, illetve klaszterek közötti ütközések feloldására. Szimulációk szerint a csomópontok mintegy 5%-ának kell csak klasztervezetônek lennie egy adott pillanatban a hálózat optimális energiafogyasztásához. A LEACH mûködése két fázisból áll, amelyek periodikusan ismétlôdnek, a két fázis együtt alkot egy menetet. I. Felépülési fázis A felépülési fázis során létrejönnek a klaszterek és megválasztódnak a klasztervezetôk. A csomópontok egy elôre definiált p (pl. 0,05) hányada választja meg magát minden menet elején klasztervezetônek a következôképpen. Egy n szenzor választ magának egy véletlen számot 0 és 1 között, és ha ez szám kisebb mint egy T(n) küszöbérték, akkor a szenzor klasztervezetônek deklarálja magát, ahol ha n ∈G. Itt r jelöli az aktuális menetszámot, G pedig azon csomópontok halmaza, amelyek még nem voltak klasztervezetôk az elmúlt (1/p) menet során. Ezek után a magukat vezetônek deklarát csomópontok értesítik a körülöttük levô csomópontokat a választás eredményérôl egy bizonyos energiaszinten küldött üzenetben. Minden csomópont azt a csomópontot választja saját klasztervezetôjének, akitôl a legnagyobb jelerôsséggel kapta az üzenetet, majd errôl informálja a választott vezetôt is. Ezután a vezetô létrehozza a megfelelô TDMA ütemezést, ahol minden hozzá tartozó csomópontnak lefoglal egy idôrést, majd az ütemezési információt elküldi a klasztertagoknak. II. Mûködési fázis A mûködési fázis során a klaszterek tagjai a mért adatot a vezetônek továbbítják, amely, miután minden adatot megkapott, az aggregátumot továbbküldi a bázisnak. A menet végén a hálózat átvált felépülési fázisba és új klaszterek alakulnak. A mûködési fázis célszerûen jóval nagyobb mint a felépülési fázis a túlterheltség csökkentése végett. A protokoll hátránya, hogy nem alkalmazható nagy területen elhelyezett hálózatnál, hiszen minden csomópontnak el kell érnie a bázist közvetlenül, továbbá feltételezi, hogy minden csomópont folytonosan küld adatot a vezetônek. Továbbá nem feltételen igaz az, hogy a vezetôk a hálózatban egyenletesen helyezkednek el, így néhány csomópontnak lehetséges, hogy nem lesz vezetôje. A protokoll feltételezi, hogy minden csomópont egyenlô kezdeti energiával rendelkezik. A legnagyobb gondot mindezek ellenére talán mégis a felépülési fázis okozta többletterhelés jelentheti. 3.5. Minden szomszédnak történô továbbítás Ezen protokollok mûködése rendkívül egyszerû. Minden csomópont a hálózatban önmaga dönt arról, hogy a kapott üzenetet továbbítania kell-e vagy sem. Ha LXI. ÉVFOLYAM 2006/12
Útvonalválasztó protokollok... igen, akkor minden szomszédjának elküldi az üzenetet (egyetlen többesszórásos üzenetben), ha nem, akkor pedig eldobja az üzenetet. Ezen protokollok képviselôje az MCFA (Minimal Cost Forwarding Algorithm) [4] protokoll. Az MCFA protokoll nagy elônye, hogy semmilyen információt sem tárolnak a csomópontok a szomszédjaikról, csak a saját maguk költségét a bázishoz viszonyítva. A protokoll két részbôl áll. Az elsô részben minden csomópont megállapítja a saját költségét a bázishoz képest, aminek érdekében a bázis elárasztja a hálózatot egy kezdetben C = 0 értékû költséget tartalmazó üzenettel. Kezdetben minden csomópont költsége végtelen. Minden Ni csomópont, amely megkapja ezt az üzenetet egy Nj csomóponttól, vár α ⋅ CNi,Nj ideig (α választásánál figyelembe kell venni a csomópontok közötti kapcsolatok késleltetését, hibáit, a csomópontok késleltetését stb.), ahol CNi,Nj az Ni és Nj csomópontok közötti kapcsolat költsége (energia, késleltetés stb.), majd frissíti az üzenetben szereplô C értéket: C = C + CNi,Nj, beállítja a saját költségét erre az új C értékre, és továbbítja a frissített üzenetet. Bebizonyítható, hogy ideális esetben (amikor α elég nagy) minden csomópont csak egyetlen ilyen üzenetet küld tovább, ami a csomópont minimális költségét tartalmazza a bázistól. A protokoll második részében minden csomópont képes már üzenetet küldeni a bázis felé a következô módon. A N küldô szenzor elhelyezi a saját CN minimális költségét a küldendô üzenetbe, és többesküldéssel elküldi azt szomszédainak. Minden M csomópont, amely hallja az üzenetet, ellenôrzi, hogy M - CN,M = CM. Ha igen, akkor M a minimális költségû útvonalon van, ezért többesküldéssel továbbküldi az üzenetet. Egyébként M eldobja az üzenetet. A protokoll hátránya, hogy minden olyan csomópont, amely vesz egy üzenetet, azt mindenképpen értelmezi is, ami többletterhelést jelent.
4. Összegzés
Köszönetnyilvánítás Az itt bemutatott munkát részben támogatta a HSN Laboratórium, a UbiSec&Sens EU projekt (www.ist-ubisecsens. org), és az OTKA (T046664). Irodalom [1] J. N. Al-Karaki, A. E. Kamal: Routing techniques in wireless sensor networks: a survey. In IEEE Wireless Communications, Vol.11, 2004. pp.6–28. [2] C. Intanagonwiwat, R. Govindan, D. Estrin: Directed Diffusion: a scalable and robust communication paradigm for sensor networks. In Proceedings of ACM MobiCom 2000, Boston, MA, pp.56–67. [3] W. Heinzelman, A. Chandrakasan, H. Balakrishnan: Energy-Efficient Communication Protocol for Wireless Microsensor Networks. In Proc. of the 33rd Hawaii International Conference on System Sciences (HICSS 2000), January 2000. [4] F. Ye, A. Chen, S. Liu, L. Zhang: A scalable solution to minimum cost forwarding in large sensor networks. In Proc. of the 10th International Conf. on Computer Communications and Networks (ICCCN 2001), pp.304–309. [5] C. Rahul, J. Rabaey: Energy Aware Routing for Low Energy Ad Hoc Sensor Networks. In IEEE Wireless Communications and Networking Conference (WCNC), March 17-21, 2002, Orlando, FL, Vol.1, pp.350–355. [6] Y. Yu, D. Estrin, R. Govindan: Geographical and Energy-Aware Routing: A Recursive Data Dissemination Protocol for Wireless Sensor Networks. UCLA Computer Science Department Technical Report, UCLA-CSD TR-01-0023, May 2001.
Jelen írásunkban a vezeték nélküli szenzorhálózatokban alkalmazott útvonalválasztó protokollokat tekintettük át röviden. A cikk elsô felében bemutattuk a létezô útvonalválasztó protokolloknak egy új osztályozási szempontrendszerét. A protokollokat rendszereztük hálózati modelljük, mûködési modelljük és célkitûzésük szerint. Táblázatokba rendezve felsoroltuk a létezô jelentôsebb útvonalválasztó protokollokat hálózati modell és cél, valamint mûködési modell szerint. A cikk második felében részletesen bemutattuk néhány konkrét protokoll mûködését. A bemutatott protokollok egy-egy protokollcsalád képviselôi voltak, ahol a családot az határozta meg, hogy a csomópontok hogyan választják a következô csomópontot a cél felé vezetô úton.
LXI. ÉVFOLYAM 2006/12
11
