Mohó útvonalválasztás számításigényének csökkentése heurisztikus módszerekkel

A mohó továbbítás a földrajzi útvonalválasztás alapját képező módszer, amit metrikus térbe ágyazott hálózatoknál használnak. Az élet számos területén fordulnak elő ilyen metrikus hálózatok, a legelterjedtebben a vezeték nélküli hálózatok körében használt a földrajzi útvonalválasztás.

A mohó útvonalválasztá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.

szerző

• 
  Sebők Tamás
  mérnökinformatikus
  nappali

konzulensek

• 
  Dr. Gulyás András
  docens, Távközlési és Mesterséges Intelligencia Tanszék
• 
  Kőrösi Attila
  tanszéki mérnök, Távközlési és Mesterséges Intelligencia Tanszék
• 
  Csernai Márton
  doktorjelölt, Távközlési és Mesterséges Intelligencia Tanszék

helyezés