BUČA: Brezžičen Umen Centraliziran Algoritem – Zadnje poročilo EN

V tem prispevku je objavljeno zaključno poročilo svojega dela med Google Summer of Code 2016.

Porabiti poletje na razvoju nodewatcherja je bilo nagrajujoče kljub naporu. Čeprav se je moj predlog nanašal le na razvoj novega algoritma, sem kmalu ugotovil da bo za sam algoritem potrebno pripraviti kopico manjših komponent. Začel sem s snovanjem skice, ki mi je dala pregled nad dolgotrajnim razvojem algoritma. Opomnik: BUČA služi kot algoritem za avtomatsko in učinkovito razporeditev WiFi frekvenc v "nasičenem" prostoru, kjer je postavljenih relativno veliko točk. Glavna prednost algoritma je v tem, da simultano dodeli kanale večim točkam in pazi, da signal ene točke ne postane premočan šum drugim točkam.

Preden sem sploh lahko začel z delom, sem moral namestiti lokalno verzijo nodewatcherja. Ob začetku dela se nisem želel vmešavati v stabilno omrežje wlan slovenija. Potreboval sem lastno; manjše omrežje za svoje teste. S tem namenom sem začel sodelovati z neprofitno organizacijo Berkeley Student Cooperative v Berkeleyu, Kaliforniji. Zagotovili so mi dostop do zgradbe z več kot 10 brezžičnimi točkami, od koder sem redno dobival podatke. Točke so zelo raznolike: prihajajo od različnih proizvajalcev in imajo različne zmožnosti. Nekatere oddajajo na 5GHz, medtem ko druge ne. Tako sem lahko razvil algoritem na okolju ki je zelo podobno skupnostnim omrežjem.

Začel sem z razvojem modula, ki je zadolžen z zbiranjem podatkov. Ko sem pridobil zanesljiv dostop do podatkov, sem lahko pričel z analizo. Pričel sem z zasnovo algoritma, ki najde "škodljive" točke (škodljive z vidika interference). Podatki o škodljivih točkah so neprecenljivi za načrtovalce omrežij, saj lahko sedaj bodisi sodelujejo z lastniki škodljivih točk bodisi premaknejo omrežje tako, da se izmaknejo škodljivemu vplivu teh točk. Zasnova algoritma je zahtevala veliko truda, saj morajo algoritmi na teh velikostih biti izjemno učinkoviti: Časovna zahtevnost algoritma je v , kar je v pojmih teorije grafov skoraj linearno.

Nato sem začel z zasnovo glavnega algoritma. Sama zasnova je trajala več kot en teden. Najprej sem razmišljal o implementaciji Beigel-Eppstein algoritma za barvanje grafov. Ta algoritem teče v času. Vendar me je zaustavila sama zahtevnost izvedbe. Algoritem se sklicuje na 19 različnih manjših primerov, ki jih lahko zaporedoma uporabimo za olajšanje celotnega problema. Namesto tega sem pogledal v izvorno kodo vodilne knjižnice obdelave grafov NetworkX in napisal lasten sistem razvrstitve točk za pravilno prioritizacijo prometa. Algoritem najprej izračuna "promet" na vsakem frekvenčnem pasu in potem izbere optimalnega za zmanjšanje skupne interference.

Ob implementaciji algoritma smo opazili, da so se posamezne točke včasih premaknile na frekvenčni razpon, ki je poslabšal delovanje tiste točke. Najprej smo mislili, da gre za napako. Vendar so ročni izračuni pokazali, da moramo včasih žrtvovati delovanje posamezne točke za skupno dobro. To se odlično sklada z našim ciljem: zagotoviti boljše delovanje za skupnost wlan slovenije.

Naslednji koraki

Največja težava z algoritmom je nezanesljivost podatkov, ki jih poberemo s točk. Potrebujemo boljši način merjenja kvalitete signala kot samo interference z drugih anten. Primer: tudi če sta dve točki skupaj, to ne bi smelo motiti algoritma, če ena izmed točk nikoli ne oddaja. Algoritem je napisal modularno, kar nam olajša menjavo meritev. Morda je bolje uporabiti število trkov paketkov.

Drugi problem je da OpenWrtjev iwinfo paket ne poroča informacij o širini kanala. S tem dodatkom bi naš algoritem bil bolj natančen. Trenutno smo prisiljeni privzeti, da vse točke uporabljajo 20MHz širok kanal.

Zadnja izboljšava se nanaša na opozorila znotraj nodewatcherja. V primeru, da se optimalni kanal v algoritmu ne sklada s trenutnim, bi na to radi opozorili lastnike točk.

Če vas zanima celoten potek razvoja, si lahko ogledate naslednje povezave: