Földrajzi útvonalválasztás heurisztikus optimalizálása

OData támogatás
Konzulens:
Dr. Gulyás András
Távközlési és Médiainformatikai Tanszék

A földrajzi útvonalválasztás gondolata először az 1980-as években merült fel rádiós hálózatokkal kapcsolatban. Jelenleg is főleg vezeték nélküli hálózatokban használják, használata az ad-hoc és szenzor hálózatok esetén a legelterjedtebb. A földrajzi útvonalválasztás azonban más területeken is használható, kutatások vannak például az alkalmazására közösségi, szociális hálók esetében is, sőt, vizsgálták a használatát Internet topológián is, ezzel új lendületet adva a földrajzi útvonalválasztás kutatásának is.

A földrajzi útvonalválasztásnál használt mohó továbbítás egy egyszerű ötletre épít: a hálózatban lokális döntések segítségével próbáljunk egy globálisan is jó útvonalat találni. A mohó útvonalválasztást nem csak az egyszerűsége (csak lokális információk kellenek a döntéshez) teszi népszerűvé, hanem az elosztott működése is. Nincs szükség a teljes hálózat ismeretére az útvonalválasztáshoz, nem kell az útvonalat előre meghatározni, az útvonal a továbbítás közben, lokális döntések következtében alakul ki.

Azonban a mohó továbbítással kapcsolatban vannak megoldandó problémák. A legnagyobb probléma a számításigénye, ugyanis a mohó algoritmus mindig a lokális optimumot keresi. Ehhez meg kell vizsgálni minden szomszédot, ezért meghatározása sok szomszéddal rendelkező csomópontok esetén költséges lehet. A dolgozatban azt mutatom meg, hogyha a továbbításnál lemondunk a lokális optimum megkereséséről, és heurisztika segítségével próbálunk egy lokálisan jó (de nem feltétlenül a legjobb) döntést hozni, akkor közel olyan jó megoldáshoz jutunk lényegesen kevesebb számítással, ezáltal sokkal gyorsabban.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.