Ebben a tanulmányban olyan különböző vezeték nélküli kommunikációs útválasztó protokollok összehasonlítása történik meg, mint az árasztás (Flooding), a gradiensalapú útválasztás (Gradient-Based-Routing, GRB) és az irányított diffúzió (Directed Diffusion, DD). A szimulációs eredmények azt mutatják, hogy – mint az várható – a GBR és a DD nagyobb teljesítményt nyújt, mint a Flooding, és a GBR és a DD hatékonysága hasonló az okos mérőalkalmazásokban. Mivel a GBR-t könnyebb megvalósítani, ez az ajánlott útválasztó megoldás egy okos mérőhálózatban.
1. Bevezetés
Az intelligens mérők elektromos energiafogyasztást mérő eszközök, melyek az energiafelhasználásról gyűjtenek információkat a lakókörnyezetben.
Egy okosmérő az összegyűjtött információkat visszaküldheti a közüzemi szolgáltatónak a számlázáshoz, és nyújthat kézi beavatkozás nélküli felügyeleti lehetőséget a szolgáltatás megkönnyítése céljából mind a fogyasztó, mind a szolgáltató felé. Ezen tulajdonság segítségével a szolgáltató képes lesz sokkal kifinomultabb képet alkotni a fogyasztói szokásokról, és a fogyasztó is azonnal értesül az eltérő energiafogyasztás következményeiről. Egy másik előny, hogy az okosmérők kétirányú kommunikációra képesek a központi rendszer felé, és ezért tudják az energiaköltségeket az aktuális árakkal megjeleníteni a fogyasztónak. A mikro-elektromechanikus rendszerek (MEMS) fejlődése lehetővé tette alacsony fogyasztású, olcsó, kis méretű, a mérést, adatgyűjtést és továbbítást elvégző érzékelő csomópontok gyártását. A vezeték nélküli érzékelőhálózat (WSN) [5] ilyen csomópontok együttműködése révén jön létre. Az okos mérőeszközök által alkotott vezeték nélküli érzékelőhálózatban a csomópontok egy adatkoncentrátor-eszközön keresztül kommunikálnak a távoli szerverrel. Az adatkoncentrátor az egyes csomópontok adatcsatornáit egyetlen célponttal köti össze az interneten keresztül. A csomópontok általában olyan központosított hálózatba szerveződnek, mint a mesh-hálózat, ahol redundáns és önjavító adatutak léteznek. A centralizált hálózat legfontosabb követelményei a következők:
- a csomópontok közötti pontos időszinkronizálási lehetőség,
- adattitkosítás,
- szabotázs elleni ellenállás,
- költséghatékony adatútválasztás.
Ami az első három követelményt illeti, ipari szabványos megoldások használhatók, a legtöbbjük elérhető alacsony szintű megvalósításban mikrovezérlő vagy SOC-környezetben. A kihívás akkor áll fenn, amikor egy specifikus útválasztó protokoll implementálása és hibamentesítése merül fel, tudván azt, hogy a vezetékes útválasztó protokollok kevésbé hatékonyak a multi-hop vezeték nélküli környezetben. Manapság olyan jól tesztelt, szabványos útválasztó protokollok léteznek, mint az AODV (Ad Hoc On-Demand Distance Vector) útválasztás, amit a ZigBee használ, vagy a DSDV (Destination-sequenced Distance-Vector) útválasztás, azonban ezek általános célú és nehézsúlyú WSN útválasztó protokollok, melyek nem veszik figyelembe az okos mérőeszközök és -hálózatok speciális követelményeit. Az okos mérőhálózat egy átlagos vezeték nélküli hálózattól több dologban különbözik:
- a csomópontok helyhez rögzítettek,
- általában kevesebb, mint 100 csomópont van egy hálózatban,
- a csomópontok nem elemmel működnek,
- az adatok összesítését végző adatkoncentrátort tartalmaz.
Ezen különbségek motiválják az egyszerű és robusztus útválasztó protokollok iránti növekvő igényt. A vezeték nélküli érzékelőhálózatok útválasztó protokolljait egyszintű, hierarchikus és helyalapú protokollokra osztályozhatjuk. Az egyszintű felépítésű útválasztó protokollok a Flooding, Directed Diffusion (DD), Gradient-Based Routing (GBR), Cougar, Spin és Minimum Cost Forwarding Algorithm.
A hierarchikus útválasztásban a csomópontok szerepe különböző. A hálózat klaszterekbe szerveződött, ahol minden egyes csomópont csak az ő illetékes klaszter-fejének válaszol, amely csomópont felelős az adatösszesítésért, az adatátvitelért a külső világ felé és a klasztermenedzsmentért. A hierarchikus útválasztási megközelítés csökkenti a forgalmat és a késleltetést a hálózaton. Hierarchikus útválasztó protokollok a Low-Energy Adaptive Clustering Hierarchy (LEACH) és Power-Efficient Gathering in Sensor Information Systems (PEGASIS).
A helyalapú útválasztás kihasználja azt, hogy ismert a csomópontok helye, és a csomagok továbbítása során jelerősség-információk is keletkeznek. Helyalapú útválasztó protokoll a Geographic Adaptive Fidelity (GAF).
Ez a tanulmány szimulációalapú megközelítést használva elemzi három, egyszintű útválasztó protokoll teljesítményét az okos mérőeszközök hálózatában: ezek a Flooding, a Directed Diffusion és a Gradient-based Routing.
A tanulmány szerkezete a következő: a második szakasz ismerteti a szimulációs keretrendszert és a módszereket, a harmadik leírja a tesztelt protokollokat, a negyedik a szimuláció eredményeit és az ötödik a tanulmány következtetéseit.
2. Szimulációs keretrendszer és módszerek
A munka során számos szimulációs kísérletet végeztünk az OMNet++ szimulátorral. Az OMNet++ egy moduláris, komponensalapú C++ szimulációs könyvtár és keretrendszer, ami alkalmas hálózati szimulációk készítésére. Egy OMNet++ szimulált hálózat hierarchikus modulokból épül fel, ahol a modulok mélysége opcionális. A keretrendszer moduljai olyan üzenetekkel kommunikálnak egymással, melyek akár összetett adatszerkezetek is lehetnek. Az üzenetek küldhetők közvetlenül egy modulnak vagy különböző csatornákon keresztül is.
A felhasználó feladata, hogy C++ nyelven meghatározza a hierarchia alsó rétegében lévő modulok viselkedését.
A keretrendszer beépített szoftverkönyvtárakkal támogatja a modulfejlesztést. A szimuláció során a felhasználó által definiált modulok mint korutinok, párhuzamosan futnak. A keretrendszer különböző felhasználói felületekkel rendelkezik, melyek megkönnyítik a hibakeresést, a szimulációk futtatását és az eredmények bemutatását.
A különböző modulok összekapcsolódását egy speciális, magas szintű nyelven, a NED (NEtwork Description) nyelven lehet definiálni. A keretrendszer lefordítja a NED modulokat C++-ra, és arra is van lehetőség, hogy a GNED kiterjesztéssel grafikusan határozzuk meg a hálózatot. A szimuláció paramétereit .ini fájlokban lehet definiálni az aktuális szimulációs folyamat futtatása előtt.
A második ábra mutat egy Python szkripttel generált .ini fájt. Az .ini fájl 9 koordinátát határoz meg egy rácson, ahol 100 m a távolság a csomópontok között.
Az OMNet++ szimulációs motor felett a MiXiM (mixed simulator) keretrendszert használtuk a vezeték nélküli hálózati útválasztó szimulálására. A több OMNet++ keretrendszert magában foglaló MiXiM projekt a mobil és vezeték nélküli szimulációk támogatására készült.
Az elődei:
- ChSim (Universitaet Paderborn)
- Mac Simulator (Technische Universiteit Delft)
- Mobility Framework (Technische Universitaet Berlin, Telecomm Networks Group)
- Positif Framework (Technische Universiteit Delft)
A MiXiM részletes modelleket kínál a rádióhullámok terjedésére, interferenciabecslésre, rádió adó-vevő energiafogyasztására és a vezeték nélküli MAC protokollokra.
A MiXim keretrendszer alkalmazási példái:
- Vezeték nélküli érzékelőhálózatok
- Testfelszíni hálózat (BAN)
- Ad-hoc hálózatok
- Közúti hálózatok
3. A tesztelt protokollok leírása
Számos protokollt javasolnak a vezeték nélküli érzékelőhálózatokban történő útválasztás megoldására. Mint azt a bevezető ismertette, ezek különböző megközelítéseket és architektúrát követnek. Ez a fejezet bemutatja az érintett protokollok implementációját.
3.1. Naiv elárasztás (Naive flooding)
Az elárasztásos algoritmusok családja a legegyszerűbb megközelítés arra, hogy megoldja az útválasztást egy lapos architektúrájú WSN-ben. Az irányítatlan naiv elárasztás esetén nincs címzés, ehelyett a csomópontok az összes vett üzenetet folyamatosan közvetítik (broadcast). A naiv elárasztásnál nincsenek irányok, a csomópontok ugyanazt a csomagot többször is megkapják a szomszédaiktól. Ez a naiv megoldás csak akkor működik rendesen, ha a csomópontok egy feszítőfára vannak rendezve. Abban az esetben, ha a hálózat topológiája kört tartalmaz, a csomagok körbe fognak járni a végtelenségig, és ha két vagy több kör is van a topológiában, az üzenetek a körbejárás közben duplikálódnak, egészen addig, míg el nem fogyasztják a teljes elérhető sávszélességet (adásvihar).
Az ellenőrzött elárasztásos protokoll foglalkozik az előbbiekben említett problémákkal. A sorszám-ellenőrzött elárasztás esetén minden csomópont hozzáragasztja a címét és egy sorszámot az üzenethez, és eltárolja a csomagot a saját dedikált memóriájában. Ha a csomópont ismételten megkapja ugyanazt a csomagot, azonnal eldobja.
A Reverse Path Forwarding (RPF) esetén a csomópontok csak előremenő irányban terjesztenek tovább üzeneteket. Ha a csomag a következő csomóponttól érkezett, akkor visszakerül az eredeti feladóhoz. A csomópontok csak akkor terjesztik tovább a csomagot, ha az üzenet ugyanazon az útvonalon van, mint az ismert visszirány. Az RPF használatához minden csomópontnak rendelkeznie kell útvonallal minden más csomóponthoz.
Az elárasztás erősségei a következők:
- nem igényel beállítást vagy topológia-karbantartást,
- nem érzékeny a hibásan működő csomópontokra,
- az üzeneteket a célhoz irányítja, ha létezik hozzájuk útvonal,
- egyszerűen implementálhatóak,
- a legrövidebb útvonalat használják (a többiek között).
Másrészt az elárasztásnak vannak gyengeségei:
- nem energia-hatékony,
- nagy a kommunikációs terhelés.
3.2. Gradiensalapú útválasztás (GRB)
Az elárasztás nem tekinthető hatékony megoldásnak, ha a cél az, hogy egyetlen nyelő vagy adatkoncentrátor felé kell továbbítani csomagokat, ahogy ez az okosmérő-hálózatok esetében fennáll. A GBR kínál egy megoldást, amelyben csak a vevő csomópont továbbít csomagot akkor, ha a feladó távolsága az adatkoncentrátortól nagyobb, mint a vevő távolsága. Az algoritmus azon a feltételezésen alapszik, hogy minden csomópont ismeri az ugrásszámban kifejezett távolságát a koncentrátortól, ahol az ugrásszám megfelel a köztes csomópontok számának, melyeken keresztül a csomagoknak át kell haladniuk, hogy elérjék a rendeltetési helyüket. A csomóponttávolságok/gradiensek feltérképezése érdekében az adatkoncentrátornak kezdeményeznie kell egy azonosítási fázist.
Az azonosítási fázis a következő négy lépésből áll:
- Először minden érzékelő csomópont beállítja a saját gradiensértékét végtelenre. R → ∞.
- A nyelő (drain) kezdeményez egy, a hálózatkiépítési fázist hirdető csomag kibocsátásával, amely tartalmazza a saját költségét, ami zéró (R sink = 0)
- Amikor egy csomópont kap egy hirdetőcsomagot, összehasonlítja a kapott gradiensértéket az ő saját jelenlegi gradienséhez mutató link költségével.
- Ha az újonnan megszerzett gradiens és a link költsége kisebb, mint a régi, a csomópont tárolja az új értéket, és kibocsát egy reklámcsomagot az új gradiensértékkel.
A link költségének kiszámításakor figyelembe kell venni a jelerősséget és a küldő csomópont energiaszintjét. A GBR-adatcsomag a küldő gradienséből, a linkköltségből és a hasznos tartalomból áll. A csomag vétele után minden csomópont a következő egyszerű algoritmust hajtja végre:
Nincs könnyű módja annak, hogy a koncentrátor értesüljön egy kieső csomópontról. Csak egy periodikusan kezdeményezett azonosítófázis oldhatja meg ezt a problémát. Egy eseménytriggerelt megoldásban a koncentrátor képes észrevenni a meghibásodott csomópont hiányzó adatait, és így egy hálózatfelépítő fázist kezdeményezni.
3.3. Irányított diffúzió (DD)
Az irányított diffúzió (DD) olyan adatközpontú protokoll, ahol az adatokat tulajdonság-érték párok írják le. A tipikus DD-alkalmazásban csak egyetlen nyelő vagy adatkoncentrátor van, amely összesíti a csomópontok adatait. Az útvonal-felderítő fázisban a nyelő egy érdeklődő broadcast-üzenetet terjeszt el a teljes érzékelőhálózatban. Ez a folyamat beállítja a gradiensértékeket a hálózatban, ahol a gradiens a tulajdonság-érték pár és az irány összege lehet. A gradiens nagysága a szomszédos csomópontoktól függően különböző lehet. A csomópontokból származó adatok elkezdenek áramlani a meredekebb emelkedés irányába [1].
A nyelő periodikusan ismétli az érdeklődőüzenet kiküldését. A cél az, hogy létrejöjjön egy feszítőfa-szerkezet. Az irányított diffúzió hátránya az, hogy az előnyös pozícióban lévő csomópontokat gyakrabban veszi igénybe. Ennek kiküszöbölésére terheléskiegyenlítő algoritmusokat használnak.
4. Szimulációs eredmények és megvitatásuk
A szimulációk különböző csomópontszámú rács- és sortopológiák használatával történtek. A csomópontok távolságát olyan módon határozták meg, hogy csak a közvetlen szomszédok voltak belül a rádió hatótávolságán.
Minden esetben a két legtávolabbi csomópont, a feladó és a vevő kommunikált periodikusan küldött üzenetekkel. Az összes többi csomópont csak továbbította a beérkezett üzeneteket.
A következő teljesítmény-mérőszámokat meghatározták meg:
- #of nodes: csomópontok száma,
- min. hop count: az üzenetet a célállomáshoz továbbító köztes csomópontok minimális száma,
- @10msgs avg hop count: az első tíz üzenet átlagos ugrásszáma,
- @10msgs total TX: hány üzenet továbbítódott a hálózaton az első tíz üzenet megérkezése során,
- @1 arrival time: első üzenet megérkezési ideje.
4.1. Sortopológia
A sortopológia nem reális megközelítés, egyetlen előnye itt az alapvető funkciókkal történő megismerkedésben rejlik.
A következő táblázatban találhatóak a sortopológia esetében vizsgált útválasztó algoritmusok szimulációs eredményei.
A következő táblázatok mutatják az eredmények összehasonlítását.
A soros elrendezés miatt a csomag számára csak olyan módon volt lehetséges végigmenni a hálózaton, hogy minden egyes csomópontot érint. A „min. hop. count” azt mutatja, hogy minden esetben volt legalább egy csomag, ami bejárta az egyenes utat.
Az 5. táblázat azt mutatja, hogy az átlagos ugrásszámláló egybeesik a minimális ugrásszámmal a kicsit szofisztikáltabb algoritmusok esetén. Tekintetbe veendő, hogy a naiv elárasztás visszafelé is továbbít üzeneteket, az ideálisnál rosszabb átlagos ugrásszámot okozva. Az alapul szolgáló rádiójel-terjedési modellt is figyelembe vettük.
A naiv esetben a hálózatban átvitt összes üzenet száma majdnem exponenciálisan növekszik, míg a GBR- és DD-algoritmusok csökkentett növekedési rátát mutatnak. Úgy tűnhet, hogy a diffúzió rosszabb, mint a GBR, ahogy azt a kétszeres mennyiségű átvitt üzenet mutatja. Ennek a jelenségnek a megmagyarázásához az irányított diffúzió esetén az összes csomópont útvonalválasztó táblázatát kell tekintetbe venni. Mivel a csomópontoknak karban kell tartaniuk saját útválasztó táblázatukat, egy nyugtázóüzenet érkezik minden küldőhöz a csomag fogadását követően. Ez a folyamat összességében kétszer annyi üzenetet von maga után. Annak ellenére, hogy adott esetben ez hátrány, a két algoritmus azonos nagyságrendben van.
Meg lehet jegyezni, hogy a teljes üzenetek száma DD esetén nem pontosan kétszer annyi, mint a gradiens esetén. Ez azért van, mert a szimuláció leállási feltétele – a tíz üzenet beérkezése – előbb következik be mint ahogy a nyugtázóüzenetek visszaérkeznek a küldő csomóponthoz, bár ez lényegesen nem befolyásolja az eredményeket.
4.2. Rácstopológia
A rácstopológia egy realisztikusabb megközelítés, mert jól közelít egy bérházkörnyezetet, ahol az okosmérőeszközök egymáshoz hasonlóan, egymástól egyenlő távolságra helyezkednek el. Az is reális, hogy az eszközök akkor vannak hatótávolságon belül, ha közvetlen szomszédai egymásnak, mint az az 6. ábrán látszik.
A következő táblázatok mutatják az eredmények összehasonlítását.
A javasolt rácselrendezésben a legrövidebb út a hálózatban a szélesség és magasság összege mínusz kettő. A „min hop count” azt mutatja, hogy minden vizsgált esetben volt legalább egy csomag, ami a legrövidebb úton ment.
Az átlagos ugrásszám jól közelíti az ideális helyzetet a GBR és DD esetében, míg a naiv megközelítés a csomópontok számának növekedésével egyre rosszabb.
A GBR és a DD az összes üzenet számában felülmúlja a naiv algoritmust, mert ezúttal a naiv algoritmus csak mérsékelt növekedést mutat a sorelrendezéses esethez képest. Ez azért van, mert a rácselrendezésben a legrövidebb út kevesebb ugrásból áll, és még a naiv megközelítés is csak ritkán képes eltalálni a legrövidebb utat. A rácselrendezés esetén a DD- és GBR-algoritmus hasonló teljesítményt mutat, annak ellenére, hogy a GBR kétszer több üzenetet igényel a működéshez.
5. Következtetések
Összefoglalva elmondható, hogy a naiv elárasztás-útválasztó protokoll elfogadhatatlanul túlterheli a hálózatot még a legegyszerűbb kísérleti esetben is, amikor az összes csomópont egy sorban van elrendezve.
A szimulációs eredmények azt mutatják, hogy a GBR és a DD az elárasztáshoz hasonlítva bármelyik topológia esetén magasabb teljesítményt mutat, és azt, hogy a GBR és DD hasonló hatékonyságú az okosmérés-alkalmazásban.
Bár a DD-nek a csomópontok növekedésével van teljesítményelőnye, ez az előny nem igazán vonzó az átlagos okosmérő-hálózatok csomópontszáma mellett, mivel a valóságban egy ilyen hálózat kevesebb mint 100 csomópontból áll.
Tekintettel arra, hogy a GBR-t könnyebb megvalósítani, ez a javasolt útválasztó megoldás az okosmérő-hálózatban.
6. Referenciák
[1] J. Al-Karaki and A. E. Kamal: “Routing techniques in wireless sensor networks: A survey,” IEEE Trans. Wireless Commun., vol. 11, pp. 6–28, Dec. 2004.
[2] Arampatzis, Th.; Lygeros, J.; Manesis, S.: "A Survey of Applications of Wireless Sensors and Wireless Sensor Networks," Intelligent Control, 2005. Proceedings of the 2005 IEEE International Symposium on, Mediterrean Conference on Control and Automation , vol., no., pp.719,724, 27-29 June 2005
[3] S. M. Abd El-kader: “Performance Evaluation for flat and hierarchical WSN routing protocols”, The Mediterranean Journal of Computers and Networks, Vol. 7, No. 3, 2011
[4] Hongseok Yoo, Moonjoo Shim, Dongkyun Kim: "A scalable multi-sink gradient-based routing protocol for traffic load balancing", EURASIP Journal on Wireless Communications and Networking, 2011
[5] Sandhya Rachamalla, Dr.Anitha Sheela Kancharla: "A survey of real-time routing protocols for wireless sensor networks", International Journal of Computer Science & Engineering Survey (IJCSES) Vol.4, No.3, June 2013
A tanulmány a Nemzeti Kutatási, Fejlesztési és Innovációs Hivatal társfinanszírozásában megvalósuló kutatás keretében készült.
