FIŠ - Fakulteta za informacijske študije

Grafovski modeli in algoritmi pri parametriziranju baznih postaj mobilne telefonije četrte generacije

Obdobje poteka: 1. 8. 2013 - 31. 7. 2016
Financer: ARRS
Sodeluje: Laboratorij za podatkovne tehnologije

Namen tega projekta je uporabiti matematično modeliranje, lastnosti in algoritme za optimalno postavitev in oblikovanje 4. generacije brezžičnih mobilnih omrežij. Projekt ima naslednje cilje:

  1. Razvoj strukturnega razumevanja maxkcut problema na določenih družinah diskovnih presečišč grafov, ki izhajajo iz 4G brezžičnih omrežnih konfiguracijskih težav. Nadalje sledijo preiskave njegovih posledic na oblikovanje 4G brezžičnega omrežja.
  2. Oblikovanje približnostnih in hevrističnih algoritmov za maxkcut problem na določenih družinah grafov in dokazati njihovo izvedljivost.
  3. Vključevanje razvitih algoritmov v sedanje 4G konfiguracije sistema brezžičnega omrežja in nadomeščanje obstoječih algoritmov, ki ne uporabljajo matematičnih struktur problema.
  4. Ocena učinkovitosti teh algoritmov na obeh simuliranih in praktičnih primerih problema.

Potreba po navedenih raziskavah se je izkazala v projektu »Pico bazna postaja četrte generacije«, katerega rezultat je bilo več patentnih prijav [LPK, LVS, LKM] in v katerem sta dva od partnerjev tega projekta ugotovila, da za več matematičnih problemov, povezanih s konfiguriranjem baznih postaj, obstaja obsežna literatura, a da ni nobenih znanih poskusov za izkoriščanje rezultatov za optimiranje parametriziranja mobilnih omrežij, prav tako pa manjkajo matematične raziskave nekaterih za uporabo zanimivih vidikov teh problemov. 

Konzorcij svetovno uveljavljenih znanstvenikov in inovatorjev se bo v tem projektu osredotočil na premostitev omenjene interdisciplinarne vrzeli. Proučili bomo problem maksimalnega k-prereza (max-k-cut), ki predstavlja matematični model za optimiranje dodeljevanja frekvenc baznim postajam v primeru omejenega števila frekvenc, v odnosu do posebnih družin diskovnih grafov, ki nastopajo pri parametriziranju mobilnih omrežij četrte generacije. Poleg tega, da je problem NP poln za splošne diskovne grafe, ni veliko znanega o problemu max-k-cut na diskovnih grafih, porojenih pri modeliranju interferenc brezžičnih omrežij četrte generacije. Upamo, da bomo pridobili novo razumevanje problema z upoštevanjem njegove geometrijske strukture in družin grafov, ki jih dobimo z malenkostnimi spremembami parametrov omrežja, ter da bo razširjeno razumevanje vodilo do novih, učinkovitih aproksimacijskih algoritmov in hevristik. Učinkovitost teh algoritmov bomo preverili na simuliranih in realnih primerih omrežij. Teoretični rezultati projekta bodo objavljeni v mednarodnih revijah in na konferencah, v primerih ustvarjanja nove intelektualne lastnine pa bomo ocenili njen poslovni potencial in jo temu primerno zaščitili s patenti.

Rezultati projekta lahko imajo znaten vpliv na učinkovitost mobilnih omrežij naslednje generacije. Partnerji zato pričakujejo, da bodo z novim interdisciplinarnim sodelovanjem izmenjali pristope k problemu, obenem pa družbi koristili s spodbujanjem trajnostnega razvoja učinkovitih mobilnih omrežij naslednje generacije in spodbujanjem uporabe bazičnih znanstvenih in tehnoloških dosežkov za večanje kakovosti življenja.

Vodja projekta: izr. prof. dr. Janez Povh