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

Zivjo!

Letos bom v sklopu projekta Google Summer of Code pomagal pri razvoju nodewatcherja. Ti prispevki bodo sluzili tako dokumentaciji mojega napredka kakor tudi izmenjavi idej o prihodnjih smereh razvoja.

nodewatcher, oprtokodno orodje za razvoj in vzdrzevanje omrezij – predvsem tistih, ki jih vzdrzujejo skupnosti prostovoljcev – je bilo sprva razvito za projekt wlan slovenija. 1336 tock dokazuje uspeh wlan slovenije in nodewatcherja obenem. Medtem ko oba projekta organsko rasteta, se je v ozadju potrebno vprasati o tehnicnih podrobnostih razdelitve brezzicnega spektruma. V "mesh" omrezjih je vcasih (v primeru izpada zicne povezave) potrebno komunicirati z drugo tocko, kar poveca nivo suma za uporabnike obeh tock. Vecinoma pa bi lahko povecali SNR (razmerje med signalom in sumom) z inteligentno porazdelitvijo spektruma med tockami, ki jih nodewatcher nadzira. Tocke so lahko bodisi usmerjevalniki (ang. router) ali pa namenske brezzicne tocke, ki prometa ne usmerjajo (primer usmerjevalnik je TP-Link 1043, primer namenske brezzicne tocke pa UniFi AP).

Teoretska osnova problema je fascinantna sama po sebi: Vsaka tocka v omrezju ima razlicen nivo suma za vsak kanal (recimo na 2.4GHz omrezju obstajajo trije kanali, ki se ne prekrivajo). K sumu prispevajo druge tocke v njeni blizini. 'Pohlepen pristop', kjer vsaka tocka poskusa cimbolj povecati svoj SNR brez ozira na ostale, je trenutno ze prisoten v industriji. Vprasanje postane bolj zanimivo, ko zelimo cimbolj povecati 'skupno dobro'. V tem primeru nosi pohlepen pristop visoko ceno anarhije. nodewatcher ima v tem primeru prednost, saj lahko prerazporedi kanale vecim tockam hkrati (v optimalnem primeru vsem tockam v okolici). Za resitev tega problema bom moral zasnovati algoritem (BUČA), ki bo nasel optimalno razporeditev kanalov med vsemi moznostmi. Ta problem je tezek zaradi eksponentnega narascanja kombinacij razporeditev s stevilom tock. Primer: samo 10 tock ima vec kot 59000 razporeditev na 2.4GHz frekvencnem pasu in vec kot 95 bilijonov na 5GHz pasu.

Tradicionalna literatura racunalniskih mrez se s tem problemom spopade z Lagrangevimi mnozilniki. Po drugi strani je algoritemska literatura blizja pribliznemu barvanju grafov. V sklopu tega projekta zelim raziskati vec pristopov. Hkrati zelim eksperimentirati z resnicnim omrezjem, ki ima vsaj 10 tock. Za testno omrezje bo potrebno zagnati lokalno verzijo nodewatcherja (trenutno se uporablja samo za poganjanje wlan slovenija projekta), kjer bom lahko popravil nekaj hroscev.

Sam algoritem BUČA bo razvit kot modul za nodewatcher, vendar ga zelim scasoma razviti neodvisno oziroma kot modul za openWRT (operacijski sistem za usmerjevalnike). Glavna tezava pri razvoju algoritma za decentraliziran sistem lezi v pomanjkanju nadzora nad tockami. Kjer smo lahko vceraj ukazovali, se je danes potrebno pogajati. Se splaca eni tocki znizati nivo svojega signala za druzbeno korist? Mogoce! Ideja obstoja omrezja, kjer tocke preko pogajanj dosezejo druzbeno optimalno razporeditev spektruma, nas zene v zavidljivo prihodnost.