Számítástudományi és Információelméleti Tanszék

 

Témakiírás

SINR (signal to interference plus noise ratio) gráfok összefüggőségének numerikus vizsgálata


Az SINR- (signal to interference plus noise ratio) gráf térbeli ad-hoc telekommunikációs hálózatok konnektivitásának modellezésére szolgál. A gráf n-dimenziós térben véletlenszerűen elhelyezkedő csúcsai a hálózat felhasználói, és egy adott felhasználó akkor tud egy másiknak üzenetet küldeni, ha a jelének erőssége kellően nagy a háttérzaj és a többi felhasználó jeleiből származó interferencia összegéhez képest. Két csúcsot pontosan akkor kötünk össze egy irányítatlan éllel, ha mindkét irányban lehetséges köztük a kommunikáció. Ha az interferenciát elhanyagoljuk és csak a zajt vesszük figyelembe, akkor az élek létezése kizárólag a felhasználók távolságától függ. Ekkor az ismert Gilbert-gráfot kapjuk, amelyet Gilbert vezetett be 1961-ben, már abban az időben is telekommunikációs motivációval. Az SINR-gráf további érdekes tulajdonsága, hogy (szemben a Gilbert-gráffal) a csúcsok fokszáma korlátos.

A modellel kapcsolatos fő kérdés, hogy - a paraméterek megválasztásától függően - perkolál-e, vagyis létezik-e a gráfban végtelen összefüggő komponens. A modellt O. Dousse, P. Thiran és társszerzőik vezették be a 2000-es évek első felében, abban az esetben, amikor a felhasználók két dimenzióban homogén módon helyezkednek el, azaz Poisson-pontfolyamatot alkotnak. 2018-20-ban B. Jahnellel közösen vizsgáltam ennek a modellnek azt a változatát, amikor a felhasználók Cox-pontfolyamatot alkotnak, vagyis egy véletlen környezetben elhelyezkedő Poisson-pontfolyamatot. Ez tartalmazza például azt az esetet, amikor valamilyen véletlen utcahálózat (pl. Poisson-Voronoi- vagy Poisson-Delaunay-tesszelláció vagy Manhattan-rács) mentén helyezkednek el a felhasználók, ami valósághűbb telekommunikációs modell, mint az eredeti Poisson-pontfolyamatos.

A modell utóbbi változatával kapcsolatban számos olyan kérdés is felmerült, amelyekre még nem sikerült matematikailag precíz választ adnunk, sőt egyes esetekben az sem világos számunkra, hogy mi a helyes válasz. A diplomamunka témája az SINR-gráf szimulációja és a kérdések minél jobb numerikus megválaszolása. Ilyen kérdések például:

* Dousse és társai a kétdimenziós Poisson-pontfolyamat esetén megfigyelték, hogy kis felhasználósűrűség esetén perkoláció nem fordulhat elő (akkor sem, ha az interferencia hatását elhanyagoljuk), majd a sűrűség növelésével a perkoláció lehetségessé válik, és kezdetben a sűrűség függvényeként növekszik a perkoláció fenntartását még lehetővé tevő maximális interferencia mértéke, de a sűrűséget tovább növelve az interferencia hatása válik dominánssá és csak egyre erősebb interferencia-kiszűrés esetén marad lehetséges a perkoláció. Igaz-e ugyanez Cox-pontfolyamatok esetén? Hogyan függ ez a viselkedés attól, hogy a térbeli távolság függvényeként hogyan csökkennek a véletlen környezet korrelációi? Ezen kérdések egy részével kapcsolatban néhány hete jelent meg P. Keeler, B. Błaszczyszyn és E. Cali új kézirata (https://arxiv.org/abs/2309.02137), így a téma tanulmányozását ezzel érdemes kezdeni.
* Matematikailag semmit nem tudunk arról az esetről, amikor a felhasználók egymáshoz képesti távolságának 0-hoz tartása esetén végtelenhez tart a leadott jel erőssége. Lehetséges-e perkoláció ebben az esetben Cox-pontfolyamat esetén? Igaz-e itt is az előbbi kérdésben feltételezett viselkedés? (Dousse és társai numerikus eredményei szerint Poisson-pontfolyamat esetén nem igaz.)
* Beláttuk, hogy Cox-pontfolyamat esetén, ha a véletlen környezet sok kis összefüggő komponensből áll, előfordulhat, hogy perkoláció kizárólag akkor lehetséges, ha az interferencia hiányában mért kapcsolódási távolságok elég nagyok. Ebben az esetben is érdekes lenne az 1. kérdést megválaszolni.
* A Manhattan-rács és hasonló modellek tanulmányozásának nehézsége, hogy a véletlen környezet korrelációi nagyon lassan csengenek le, ezért ezek a modellek matematikailag nehezen kezelhetők. A. D. Vu, B. Jahnel és S. Jhawar tavalyi cikke szerint interferencia hiányában bizonyos paraméterválasztások esetén előfordul perkoláció. Igaz-e ugyanez az SINR-gráfban is?
* B. Jahnellel közös cikkünkben több esetben beláttuk, hogy perkoláció lehetséges abban az esetben is, amikor a felhasználók véletlen (független, azonos eloszlású) ,,hangerősségekkel'' (fadings) rendelkeznek. Azonban itt legtöbbször fel kellett tennünk, hogy a hangerősségek korlátosak vagy legalábbis véges exponenciális momentumokkal rendelkeznek. Logikusan hangzik, hogy a nagy valószínűséggel nagy értékeket felvevő hangerősség nem gátolja a perkolációt. Igaznak tűnik-e ez szimulációk alapján?
* A Poisson-pontfolyamat esetén (bárhány dimenzióban) már ismert, hogy bármely olyan felhasználósűrűség esetén, ahol interferencia hiányában fennáll a perkoláció, kis mértékű interferencia hozzáadásával a perkoláció fenntartható. Igaz-e ez a Cox-pontfolyamatok esetében is, vagy előfordulhat, hogy egy bizonyos felhasználósűrűség-tartományban ugyan interferencia nélkül van perkoláció, de bármilyen kicsi pozitív interferencia figyelembevétele esetén már nincs?
* Mi az a lehető legkisebb fokszámkorlát, amely mellett perkoláció már lehetséges? Dousse és társai szimulációi szerint a kétdimenziós Poisson-pontfolyamat esetén, ha a maximális fokszám kb. 50, akkor már van végtelen összefüggő komponens. Lehet-e ezt a korlátot csökkenteni, illetve mi a helyzet a Cox-pontfolyamatok esetén?


Munkanyelv: angol.

Dr. Tóbiás András

tobiasandrasj@gmail.com