In vijf stappen naar een betere mobiele dekking

19 juni 2009

Het probleem dat hen parten speelt, is dat je geen zelfde frequenties moet toewijzen aan zenders die zich in elkaars invloedssfeer bevinden. Dat veroorzaakt storing. Maar erg veel keuze is er niet, want het aantal beschikbare frequenties is beperkt. Wat is wijsheid?

Het vinden van de optimale verdeling van frequenties over gegeven zenders is een notoir lastig probleem. Feitelijk is het een geval uit de categorie met de koppigste wiskundige problemen: de klasse der NP-volledige problemen, waartoe ook het beruchte handelsreizigerprobleem behoort.

Dergelijke ‘combinatorische optimaliseringsproblemen’ zijn oplosbaar zolang het aantal elementen (zenders en frequenties, in dit geval) beperkt is, maar met het stijgen van het aantal zenders neemt de klus rap in omvang toe. Zo rap dat het al snel ondoenlijk wordt, dit als gevolg van een zogeheten combinatorische explosie van het aantal te evalueren opties.

Om zo’n explosie te vermijden, hebben de mobiele-telecomoperators het streven naar de enige ‘werkelijk optimale’ toewijzing allang opgegeven. Ze prijzen zich gelukkig met iets wat in de praktijk niet tot al te veel klachten leidt.

Maar deze week vond in Amsterdam een promotie plaats die hun aandacht verdient. Erik Jan van Leeuwen verdedigde zijn proefschrift ‘Optimization and Approximation on Systems of Geometric Objects’, waarin hij uit de doeken doet hoe je zonder tot sint-juttemis door te hoeven rekenen de optimale oplossing gegarandeerd tot op 10 procent nauwkeurig kunt benaderen. En dat is stukken minder slecht dan hetgeen waarmee de telecombedrijven hun klanten tot dusverre tevreden proberen te houden.

Van Leeuwen gaat – in een notendop – als volgt te werk:

  1. Teken over de landkaart met zenders horizontale lijnen met een afstand van bijvoorbeeld 10 meter;
  2. Zoek per strook de voordeligste oplossing. Dat kan redelijk snel, gebruikmakend van de lineaire structuur van een strook;
  3. Alle strookoplossingen samen leveren na correcties voor ‘grensconflicten’ een globale oplossing;
  4. Herhaal de stappen 2 en 3 negen maal voor stroken die telkens één tiende zijn opgeschoven (de tiende verschuiving hoef je niet door te rekenen omdat deze gelijk is aan de eerste);
  5. Selecteer de voordeligste van de tien gevonden oplossingen.


Het lijkt misschien nog een heel gedoe, maar met honderden zenders en tientallen frequenties is het altijd nog tienduizenden malen minder werk dan domweg alles uitproberen, wat vooralsnog de enige weg naar de werkelijk optimale oplossing is. Toch is de verdienste op grond waarvan Van Leeuwen de doctorstitel kon opeisen, niet in de eerste plaats het bedenken van dit efficiënte algoritme. De echte harde wiskundige noot was te bewijzen dat het klopt en dat het nooit een antwoord kan opleveren dat verder dan een vooraf instelbaar percentage verwijderd is van het werkelijke optimum.

Volgens Van Leeuwens promotor, professor Lex Schrijver van het Centrum Wiskunde & Informatica en de UvA, is er tot dusverre geen contact geweest met de telecomindustrie. “Het gaat ons om de conceptuele kant van de zaak. De kennis die we hiervoor ontwikkelden is veel breder toepasbaar, bijvoorbeeld in sensornetwerken en wellicht nog in tal van andere gebieden.”

Ook zijn promovendus betoont zich – via een feilloos werkende mobiele verbinding – primair wetenschappelijk gedreven: “Ik vind de wiskundige kant gewoon spannender dan de economische kant van de zaak, maar het lijkt mij wel heel interessant om eens met bijvoorbeeld de telecomindustrie te praten om te zien in hoeverre zo’n verregaand wiskundige benadering ook in de praktijk bruikbaar is”.

 
Lees het hele artikel
Je kunt dit artikel lezen nadat je bent ingelogd. Ben je nieuw bij AG Connect, registreer je dan gratis!

Registreren

  • Direct toegang tot AGConnect.nl
  • Dagelijks een AGConnect nieuwsbrief
  • 30 dagen onbeperkte toegang tot AGConnect.nl

Ben je abonnee, maar heb je nog geen account? Laat de klantenservice je terugbellen!